CodeForces - 1463E（拓扑排序）

[题目链接](https://vjudge.net/problem/CodeForces-1463E) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=3e5+5; int n,k,fa[M],siz[M],vis[M],nxt[M]; vector<int> vt[M],ans; deque<int> q; int fnd(int x){return fa[x]==x?x:(fa[x]=fnd(fa[x]));} int check() { for(int i=1;i<=n;i++) { int x=fnd(i); if(vis[x])continue; while(nxt[x]) { vis[x]=1; for(auto y:vt[x]) { if(fnd(y)!=fnd(x))continue; if(vis[y])return 0; else siz[fnd(x)]--; } x=nxt[x]; } } return 1; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { fa[i]=i; siz[i]=1; int x;scanf("%d",&x); vt[x].push_back(i); } int bad=0; for(int i=1;i<=k;i++) { int x,y;scanf("%d%d",&x,&y); nxt[x]=y; int t1=fnd(x),t2=fnd(y); if(t1==t2){bad=1;continue;} fa[t2]=t1; siz[t1]+=siz[t2]; } if(bad)return 0*printf("0\n"); if(!check())return 0*printf("0\n"); q.push_back(0); for(int i=1;i<=n;i++)vis[i]=0; while(!q.empty()) { int x=q.front();q.pop_front(); if(x)ans.push_back(x); if(nxt[x])q.push_front(nxt[x]); for(auto y:vt[x]) { y=fnd(y); if(!vis[y])siz[y]--; if(!vis[y]&&!siz[y])q.push_back(y),vis[y]=1; } } int m=ans.size(); if(m==n)for(auto p:ans)printf("%d ",p); else printf("0\n"); return 0; } ```