大概类似拓扑排序 找入度为0的点 然后删 最后剩下偶环 任选一边就好了
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } inline void write(int x){ if (x>=10) write(x/10); putchar('0'+x%10); } const int N=200005; int n,a[N]; int tag[N],deg[N]; int Q[N],l,r; int main(){ int x; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); n<<=1; for (int i=1;i<=n;i++) read(a[i]),deg[a[i]]++; for (int i=1;i<=n;i++) if (!deg[i]) Q[++r]=i; while (l<r){ int u=Q[++l]; tag[u]=1; if (tag[a[u]]==0){ tag[a[u]]=2; if (!(--deg[a[a[u]]])) Q[++r]=a[a[u]]; } } for (int i=1;i<=n/2;i++) if (!tag[i]) tag[i]=1; for (int i=1;i<=n;i++) if (tag[i]==1) write(i),putchar(' '); return 0; }