AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
自由周某
,
2020-08-24 09:55:05
,
所有人可见
,
阅读 390
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
int e[N], ne[N], d[N], h[N], q[N], id;
bool st[N];
int n, m;
void add(int a, int b){
e[id] = b;
ne[id] = h[a];
h[a] = id++;
d[b]++;
}
int ans[N];
int cnt = 0;
void bfs(){
int hh = 1 , tt = 1;
bool found = false;
for(int i = 1; i <= n; i++)
if(d[i] == 0) {q[++tt] = i; found = true;}
if(!found) cout << -1;
else
while(hh <= tt){
int k = q[hh++];
if(!st[k])
{
if(k) ans[cnt++] = k;
st[k] = true;
}
for(int i = h[k]; i != -1; i = ne[i]){
int r = e[i];
d[r] --;
if(d[r] == 0) q[++tt] = r;
}
}
}
int main(){
memset(h, -1, sizeof h);
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
add(a, b);
}
bfs();
if(cnt == n)
for(int i = 0 ; i < n; i++) cout << ans[i] << " ";
else cout << -1 ;
return 0;
}