Algorithms/Topologicalsort.java at master · ravikiradoo/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# Algorithms
import java.io.*;
import java.util.*;

class Edge
{
    int v;
    int weight;
}

class Graph{

    int V;
    ArrayList<Edge> Edges[];
    Stack stack=new Stack();
    boolean visited[];
	Graph(int v)
	{
	    V=v;
	    visited=new boolean[V];
	    Edges=new ArrayList[V];
	    for(int i=0;i<V;i++)
	    Edges[i]=new ArrayList<Edge>();


	}

public void	AddEdge(int a,int b,int weight)
	{
	    Edge edge=new Edge();
	    edge.v=b;
	    edge.weight=weight;
	    Edges[a].add(edge);

	}

	public Stack TopologicalSort()
	{

	 for(int i=0;i<V;i++)
	 {
	     if(visited[i]==false)
	     Topological(i);

	 }

	    return stack;

	}
	public void Topological(int v)
	{
	    visited[v]=true;

	    for(int i=0;i<Edges[v].size();i++)
	    {
	        int u=Edges[v].get(i).v;
	        if(visited[u]==false)
	        Topological(u);

	    }
	    stack.push(v);
	}

}
class Main
{
    public static void main(String args[])
    {
        Scanner scan = new Scanner(System.in);


        int n= scan.nextInt();
        Graph graph=new Graph(n);

        int e=scan.nextInt();

          for(int i=0;i<e;i++)
          {
             graph.AddEdge(scan.nextInt(),scan.nextInt(),scan.nextInt());

          }
          Stack stack=graph.TopologicalSort();

          while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
   }

    }