Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. private int[] getResult() {
  2. int d[] = new int[n + 1];
  3. for (int i = 0; i <= n; i++) {
  4. d[i] = -1;
  5. }
  6. d[source] = 0;
  7.  
  8. boolean viz[] = new boolean[n + 1];
  9. LinkedList<Integer> list = new LinkedList<>();
  10. list.add(source);
  11. viz[source] = true;
  12. int aux_node;
  13. while(!list.isEmpty()) {
  14. aux_node = list.poll();
  15. for(int i = 0; i < adj[aux_node].size(); i++) {
  16. if(viz[adj[aux_node].get(i) ] == false) {
  17. list.add(adj[aux_node].get(i));
  18. viz[adj[aux_node].get(i)] = true;
  19. d[adj[aux_node].get(i)] = d[aux_node] + 1;
  20. }
  21. }
  22. }
  23. return d;
  24. }
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31. private ArrayList<Integer> getResult() {
  32.  
  33.  
  34. ArrayList<Integer> topsort = new ArrayList<>();
  35. boolean viz[] = new boolean[n + 1];
  36. int[] nr_muchii = new int[n + 1];
  37. for(int i = 1; i <= n; i++) {
  38. for(int x : adj[i]) {
  39. nr_muchii[x] += 1;
  40. }
  41. }
  42.  
  43. LinkedList<Integer> Q = new LinkedList<>();
  44.  
  45. for(int i = 1; i <= n; i++) {
  46. if(nr_muchii[i] == 0)
  47. Q.add(i);
  48. }
  49.  
  50. int aux_node;
  51. while(!Q.isEmpty()) {
  52. aux_node = (int) Q.poll();
  53. viz[aux_node] = true;
  54. topsort.add(aux_node);
  55. for(int x : adj[aux_node]) {
  56. nr_muchii[x] -= 1;
  57. if(viz[x] == false && nr_muchii[x] == 0)
  58. Q.add(x);
  59. }
  60. }
  61.  
  62. return topsort;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement