AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
白小黑
,
2023-11-14 15:30:22
,
所有人可见
,
阅读 49
时间复杂度o(n+m)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], idx;
int n,m;
int q[N],d[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool f(){
int k=0;
//找到所有入度为0的点加到数组q中
for(int i=1;i<=n;i++){
if(!d[i]) q[k++]=i;
}
//遍历所有入读为0的出边;
int i=0;
while(i<=k){
int x=q[i++];
for(int j=h[x];j!=-1;j=ne[j]){
int s=e[j];
//删除x->s这条边,s的入度减一。
d[s]--;
if(!d[s]) q[k++]=s;
}
}
return k==n;
}
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);
d[b]++;
}
if(f()){
for(int i=0;i<n;i++) cout<<q[i]<<" ";
}else {
cout<<-1<<endl;
}
return 0;
}