-
Notifications
You must be signed in to change notification settings - Fork 1
/
TopologicalSorting.cpp
62 lines (62 loc) · 1.1 KB
/
TopologicalSorting.cpp
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
#include<bits/stdc++.h>
using namespace std;
#define white 1
#define gray 2
#define black 3
#define NIL -1
int vis[1000];
stack<int>res;
class Graph
{
int V;
list<int> *adj;
public:
Graph(int V);
void addedge(int v,int w);
void topsort(int u);
};
Graph::Graph(int V)
{
this->V=V;
adj= new list<int>[V];
}
void Graph::addedge(int v,int w)
{
adj[v].push_back(w);
}
void Graph::topsort(int u)
{
// cout<<u<<" ";
vis[u]=gray;
list<int>::iterator it;
for(it=adj[u].begin();it!=adj[u].end();it++)
{
if(vis[*it]==white)
topsort(*it);
}
vis[u]=black;
res.push(u);
}
int main()
{
Graph g1(8);
g1.addedge(0,2);
g1.addedge(1,2);
g1.addedge(1,3);
g1.addedge(2,4);
g1.addedge(3,5);
g1.addedge(4,5);
g1.addedge(4,7);
g1.addedge(5,6);
for(int i=0;i<10;i++)
vis[i]=white;
for(int i=0;i<8;i++)
if(vis[i]==white)
g1.topsort(i);
while(!res.empty())
{
cout<<res.top()<<" ";
res.pop();
}
return 0;
}