蓝桥杯[发现环] 发表于 2018-05-17 | 分类于 算法 , DFS | 阅读数 次 链接:蓝桥杯[发现环] 题解 注意起点不一定在环上…太菜了…一头栽进坑 因为根不一定是1 123456789101112131415161718192021222324252627282930#include<iostream>#include<cmath>#include<cstdlib>#include<cstdio>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=3e5+7;int to[N],nxt[N],head[N],in[N],ans[N],len,cnt,n,cl;inline void adde(int a,int b){to[++cnt]=b;nxt[cnt]=head[a];head[a]=cnt;}int dfs(int u,int f){ in[u]=1; for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=f){ if(in[v]){cl=v;return 1;} if(dfs(v,u))return 1; } return in[u]=0;}inline void ce(int x){in[x]=0;for(int i=head[x],v;i;i=nxt[i]){if(v==cl)return ;if(in[v])ce(v);}}int main(){ scanf("%d",&n); rep(i,1,n){int a,b;scanf("%d%d",&a,&b);adde(a,b);adde(b,a);} dfs(1,0); if(cl!=1)ce(1); rep(i,1,n)if(in[i])printf("%d ",i); return 0;}