Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.22 KB | None | 0 0
  1. package com.Shubhra;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Scanner;
  5. import java.util.Stack;
  6.  
  7. public class Graph {
  8.  
  9. int Number;
  10. ArrayList<Node> Vertices[];
  11.  
  12. public Graph(int Number)
  13. {
  14. this.Number = Number;
  15. Vertices = new ArrayList[Number+1];
  16.  
  17. for (int i = 1; i < Vertices.length; i++) {
  18. Vertices[i] = new ArrayList<>();
  19.  
  20. }
  21. }
  22.  
  23. public void CreateEdge(Node n1, Node n2)
  24. {
  25. Vertices[n1.index].add(n2);
  26. }
  27.  
  28. public void DFS(Node startNode){
  29.  
  30. startNode.visited = true;
  31.  
  32. for (Node n : Vertices[startNode.index]) {
  33.  
  34. if (n.visited != true) {
  35. DFS(n);
  36. }
  37.  
  38. }
  39.  
  40. System.out.println(startNode.v);
  41.  
  42. }
  43.  
  44. Stack<Node> topoStack = new Stack<>();
  45. public void TopoSort(Node startNode){
  46.  
  47. startNode.visited = true;
  48.  
  49. for (Node n : Vertices[startNode.index]) {
  50.  
  51. if (n.visited != true)
  52. {
  53. TopoSort(n);
  54.  
  55. }
  56.  
  57.  
  58. }
  59. topoStack.push(startNode);
  60.  
  61. }
  62.  
  63. public void OrderingTasks()
  64. {
  65. //System.out.println(Vertices[4]);
  66. for (int c = 1; c < Vertices.length; c++)
  67. {
  68. //System.out.print(c);
  69. if (Vertices[c].get(0).visited)
  70. {
  71. continue;
  72. } else {
  73. TopoSort(Vertices[c].get(0));
  74. }
  75. }
  76.  
  77. while (topoStack.isEmpty() == false) {
  78. System.out.println(topoStack.pop().v);
  79. }
  80.  
  81. }
  82.  
  83. public static void main(String[] args)
  84. {
  85. Scanner sc = new Scanner(System.in);
  86. int n = sc.nextInt();
  87. int m = sc.nextInt();
  88.  
  89. Graph g = new Graph(n);
  90.  
  91. Node[] nodes = new Node[n+1];
  92. for(int i = 1;i<=n;i++)
  93. {
  94. nodes[i] = new Node(i,false,i);
  95. g.CreateEdge(nodes[i],nodes[i]);
  96. }
  97.  
  98.  
  99. for (int i = 0;i<m;i++)
  100. {
  101. int n1 = sc.nextInt();
  102. int n2 = sc.nextInt();
  103. //System.out.println(nodes[n1].v);
  104. g.CreateEdge(nodes[n1],nodes[n2]);
  105. }
  106.  
  107. g.OrderingTasks();
  108. }
  109.  
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement