Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.Shubhra;
- import java.util.ArrayList;
- import java.util.Scanner;
- import java.util.Stack;
- public class Graph {
- int Number;
- ArrayList<Node> Vertices[];
- public Graph(int Number)
- {
- this.Number = Number;
- Vertices = new ArrayList[Number+1];
- for (int i = 1; i < Vertices.length; i++) {
- Vertices[i] = new ArrayList<>();
- }
- }
- public void CreateEdge(Node n1, Node n2)
- {
- Vertices[n1.index].add(n2);
- }
- public void DFS(Node startNode){
- startNode.visited = true;
- for (Node n : Vertices[startNode.index]) {
- if (n.visited != true) {
- DFS(n);
- }
- }
- System.out.println(startNode.v);
- }
- Stack<Node> topoStack = new Stack<>();
- public void TopoSort(Node startNode){
- startNode.visited = true;
- for (Node n : Vertices[startNode.index]) {
- if (n.visited != true)
- {
- TopoSort(n);
- }
- }
- topoStack.push(startNode);
- }
- public void OrderingTasks()
- {
- //System.out.println(Vertices[4]);
- for (int c = 1; c < Vertices.length; c++)
- {
- //System.out.print(c);
- if (Vertices[c].get(0).visited)
- {
- continue;
- } else {
- TopoSort(Vertices[c].get(0));
- }
- }
- while (topoStack.isEmpty() == false) {
- System.out.println(topoStack.pop().v);
- }
- }
- public static void main(String[] args)
- {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- int m = sc.nextInt();
- Graph g = new Graph(n);
- Node[] nodes = new Node[n+1];
- for(int i = 1;i<=n;i++)
- {
- nodes[i] = new Node(i,false,i);
- g.CreateEdge(nodes[i],nodes[i]);
- }
- for (int i = 0;i<m;i++)
- {
- int n1 = sc.nextInt();
- int n2 = sc.nextInt();
- //System.out.println(nodes[n1].v);
- g.CreateEdge(nodes[n1],nodes[n2]);
- }
- g.OrderingTasks();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement