蓝桥杯[发现环]

发表于 | 分类于 ， | 阅读数 次

链接:蓝桥杯[发现环]

题解

  • 注意起点不一定在环上…太菜了…一头栽进坑
  • 因为根不一定是1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 long
using 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;
}