AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
南骁
,
2022-08-07 00:02:26
,
所有人可见
,
阅读 113
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a,int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort(){
int hh = 0,tt = -1;
for(int i = 1; i <= n;i++)if(d[i]==0)q[++tt] =i; //遍历所有的点,入度0的入队
while(hh<=tt){
int t = q[hh++];
for(int i = h[t];i != -1;i = ne[i]){
int j = e[i];
d[j]--;//把入度的边删掉
if(d[j]==0)q[++tt] = j;//入度0符合条件入队
}
}
return tt == n-1;//判断是否所有的点都入队了
}
int main(){
cin>>n>>m;
memset(h, -1, sizeof h);
memset(d, 0, sizeof d);
for(int i = 0;i < m;i++){
int a,b;
cin>>a>>b;
add(a, b);
d[b]++;
}
if(topsort()){
for (int i = 0; i < n; i ++ )cout<<q[i]<<' ';
}
else{
puts("-1");
}
return 0;
}