有向图的拓扑序列
这题最特别的一点就是用到了数组模拟队列
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=1e5+10; int e[N],ne[N],h[N],idx,d[N],n,m; int q[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool top_sort() { int head=0,tail=-1; for(int i=1;i<=n;i++)if(d[i]==0)q[++tail]=i; while(head<=tail) { auto t=q[head++]; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0)q[++tail]=j; } } if(tail==n-1)return true; return false; } int main() { cin>>n>>m; memset(h,-1,sizeof(h)); for(int i=0;i<m;i++) { int a,b; cin>>a>>b; add(a,b); d[b]++; } if(top_sort())for(int i=0;i<n;i++)cout<<q[i]<<" "; else cout<<-1<<endl; }
