蓝桥杯2017年第八届真题-发现环

解题思路:通过读题发现，只有一个环，那么就可以使用tarjan将这一个环缩成一个点,将这一个点中的点输出即可

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int next;
}mp[200005];
int head[200005];
int dfn[200005];
int low[200005];
int cnt=0;
stack<int>sta;
void add(int a,int b)
{
	mp[++cnt].to=b;
	mp[cnt].next=head[a];
	head[a]=cnt;
}
int dfs_num=0;
bool vis[200005];
vector<int>vec;
int caler[200005];
int ans_node;
void tarjan(int u,int fa)
{
	low[u]=dfn[u]=++dfs_num;
	vis[u]=1;
	sta.push(u);
	//cout<<u<<endl;
	for(int i=head[u];i;i=mp[i].next)
	{	
		int v;
		v=mp[i].to;
		if(v==fa)continue;
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])
		{
			low[u]=min(low[u],low[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		int v;
		while(!sta.empty())
		{
			v=sta.top();
			sta.pop();
			caler[v]=u;
			vis[v]=0;
			if(v==u)
			{
				break;
			}
			ans_node=u;
		}
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjan(i,0);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(caler[i]==ans_node)
		{
			cout<<i<<' '; 
		}
	}
	return 0;
}