-
Notifications
You must be signed in to change notification settings - Fork 0
/
Topological sort 1.cpp
55 lines (50 loc) · 1.05 KB
/
Topological sort 1.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
#include<bits/stdc++.h>
using namespace std;
#define white 1
#define gray 2
#define black 3
#define Max 10000
int adj[100][100], color[Max],startingtime[Max],finisingtim[Max];
int node, edge, Time = 1;
stack<int> s;
void dfsvisit( int x) {
startingtime[Time] = Time++;
color[x] = gray;
for ( int i = 0; i<node; i++) {
if ( adj[x][i] == 1 ){
if ( color[i] == white) {
dfsvisit(i);
}
}
}
color[x] = black;
finisingtim[x] = Time++;
s.push(x);
}
void dfs () {
for ( int i = 0; i<node; i++) {
color[i] = white;
}
for ( int i = 0; i<node; i++) {
if (color[i] == white) {
dfsvisit(i);
}
}
}
int main() {
//freopen("in.txt","r",stdin);
cin>>node>>edge;
for ( int i = 0; i<edge; i++) {
int x, y;
cin>>x>>y;
adj[x][y] = 1;
}
dfs();
cout<<"after topological sort the area element"<<endl;
while( !s.empty()){
cout<< s.top()<< " ";
s.pop();
}
cout<<endl;
return 0;
}