基环树

以下内容参考：https://www.cnblogs.com/fusiwei/p/13815549.html

概念

基环树也叫环套树，标准定义是一个有 \(n\) 个节点 \(n\) 条边的联通图，如果不是联通的，则称其是一个基环树森林。

例如下面这张图就是一个基环树。

如果我们把里面的环内的任意一条边给断开，他就会变成一棵树，如果把这个环全部断掉则会变成一个森林。

内向树和外向树

所谓内向树的定义是每个点有且只有一条出边。也就是这棵树给人的大体感觉是向内的。

所谓外向树的定义是每个点有且只有一条入边。也就是这棵树给人的大题感觉是外向的。

例如下面这个就是一棵内向树。

而下面这个就是一棵外向树。

基环树题型

根据上面的定义介绍，我们可以感觉到，基环树虽然被单独拿出来讨论，但是其本质上还是一个比较简单且好理解的数据结构之一。所以它只能适当地提升题目难度，并不能说一个树的题变成基环树就大大增强了。

一些经典例题有：基环树直径、基环树两点之间距离，基环树DP，等。

这些模型的解决通法一般是：断环成树，然后将若干棵树处理好之后，再考虑环对答案的影响。也就是将环、树分开讨论解决问题。这时，用”环套树“这个名词来形容基环树，很是容易理解。

P8655 [蓝桥杯 2017 国 B] 发现环

题目的意思简洁明了，就是让你找一个环，并且要按编号从小到大输出环内的所有点。

我们可以用并查集来判断是否有环，我们边加边边合并，如果当前两个点已经在同一集合内的话，说明已经有环了，且环的所有边都已经加进去了。然后我们再跑一遍 dfs 后直接 sort 一下输出即可。

#include<bits/stdc++.h>
#define int long long
#define N 1001000
using namespace std;
int n,f[N],vis[N];
vector<int>v[N],ans;
inline int fid(int x)
{
	if(f[x]==x)return x;
	return f[x]=fid(f[x]); 
}
inline void merge(int x,int y)
{
	int xx=fid(x);
	int yy=fid(y);
	if(xx!=yy)
	  f[xx]=yy;
}
inline void dfs(int s,int t)
{
	if(s==t)
	{
		sort(ans.begin(),ans.end());
		for(int i=0;i<ans.size();i++)
			cout<<ans[i]<<' ';
		exit(0);
	}
	for(int i=0;i<v[s].size();i++)
	{
		int u=v[s][i];
		if(!vis[u])
		{
			vis[u]=1;
			ans.push_back(u);
			dfs(u,t);
			ans.pop_back();
			vis[u]=0;
		}
	}
}
signed main()
{
	int a,b;
	cin>>n;
	for(int i=1;i<=n;i++)
	  f[i]=i;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
		if(fid(a)!=fid(b))
		  merge(a,b);
		else break;
	}
	vis[a]=1;
	ans.push_back(a);
	dfs(a,b);
	return 0;
}