基环树的定义:具有n个点n条边的连通图
/*核心思想:对某一点进行一个方向延伸并记录的操作,
若该点在环中,则沿着另一方向时一定会发现这方向的第一个点已被记录且由该点走过,
然后借由反向数组存储环*/
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> vis, isin, fa, loop;
int ti;
vector<vector<int>> g;
//溯源找环法,看一个点能否延伸到自己
void dfs(int u)
{
vis[u] = ++ ti;//记录深浅
for (auto &v : g[u]) //g[u]为u到散发的点
{
if (v == fa[u]) continue;
if (vis[v])//指向经过的点,找到回路
{
if (vis[v] > vis[u])//判断从深到浅
{
for (; v != fa[u]; v = fa[v])
{
loop.push_back(v);//存环
isin[v] = 1;
}
}
}
else {
fa[v] = u;
dfs(v);
}
}
}
int main()
{
cin >> n;
/*初始找环*/
ti = 0;
fa = vector<int> (n + 1);
vis = fa, isin = fa;
loop.clear();
g = vector<vector<int>> (n + 1);
//处理输出,构建图
for (int i = 0; i < n; i ++ )
{
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1);//任意点即可
//输出环
cout << "H: ";
for (int x : loop) cout << x << ' ';
puts("");
return 0;
}