简介：

基环树，也是环套树，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。因此，对基环树的处理大部分就是对树处理和对环处理。

基环树找环

 1 vector<int> G[MAXN]; //基环树
 2 
 3 int fa[MAXN];        //dfs时的父亲
 4 int dfn[MAXN], idx;  //访问的时间
 5 int loop[MAXN], cnt; //环
 6 
 7 void get_loop(int u) {
 8     dfn[u] = ++ idx;
 9     for (int i = 0; i < G[u].size(); i ++) {
10         int v = G[u][i];
11         if(v == fa[u]) continue ;
12         if(dfn[v]) {
13             if(dfn[v] < dfn[u]) continue ;
14             loop[++ cnt] = v;
15             for ( ; v != u; v = fa[v])
16                 loop[++ cnt] = fa[v];
17         } else fa[v] = u, get_loop(v);
18     }
19 }

关于dfn[v] < dfn[u]的理解，黑色为节点编号，红色为dfs序，箭头表示父节点，只有当5节点在遍历到6时才能加环，给个简单的反例帮助理解

当一次遍历后u=4时v=1，此时dfn[v] < dfn[u]，进入for循环后会发现因为fa[1]不存在，所以进入了死循环

（未完待续）