Topological sort - DFS implementation
作者:
lazy_go
,
2022-04-06 22:18:36
,
所有人可见
,
阅读 143
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int topoNum;
enum COLOR {
WHITE, GRAY, BLACK
};
COLOR* color;
int* topoNums;
bool has_cycle;
stack<int> res;
void topo_order(const vector<vector<int> >& adj, int u){
color[u] = GRAY;
for(int v : adj[u]){
if(color[v] == WHITE){
topo_order(adj, v);
if(has_cycle)return;
}else{
if(color[v] == GRAY){
has_cycle = true;
return;
}
}
}
topoNum --;
topoNums[u] = topoNum;
color[u] = BLACK;
res.push(u);
}
void dfs_wrapper(const vector<vector<int> >& adj, int n){
for(int i = 1; i <= n; i ++)color[i] = WHITE;
for(int i = 1; i <= n; i ++){
if(color[i] == WHITE){
topo_order(adj, i);
}
}
}
void print(int n){
while(n--){
int t = res.top();
res.pop();
printf("%d ", t);
}
puts("");
}
void addArc(int x, int y, vector<vector<int> >& adj){
adj[x].push_back(y);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
vector<vector<int> > adj;
adj.resize(n+1);
topoNum = n + 1;
color = new COLOR[n+1];
topoNums = new int[n+1];
for(int i = 1; i <= m; i ++){
int x, y;
scanf("%d%d", &x, &y);
addArc(x, y, adj);
}
dfs_wrapper(adj, n);
if(has_cycle)puts("-1");
else print(n);
delete[] topoNums;
delete[] color;
return 0;
}