概念

基环树 = n个点n条边的图 = 1棵树 + 1个环
在这里插入图片描述
无向树(N点N边无向图)

在这里插入图片描述
外向树(每个点入度=1)

在这里插入图片描述
内向树(每个点出度=1)
以上三种树有十分优秀的性质，就是可以直接将环作为根。就可以对每个环的子树进行单独处理，最后再处理环

找环

拓扑排序

处理无向图
可以找出环上的所有点
入度大于等于2的点就是环上的点
code

void topsort(){
    int l=0,r=0;
    for (int i=1;i<=n;i++) 
      if(in[i]==1) q[++r]=i;
    while(l<r) {
        int now=q[++l];
        for (int i=ls[now];i;i=a[i].next){
            int y=a[i].to;
            if(in[y]>1){
                in[y]--;
                if(in[y]==1) q[++r]=y;
            }
        }
    }
}

dfs

处理有向图，码量小
mark就是环上的一个点

void check_c(int x)
{
    v[x]=true;
    if(v[d[x]]) mark=x;
    else check_c(father[x]);
    return;
}

问题解决方法：

断环法：

每次断开环上的一条边跑一遍答案，然后去最大值
适合：数据较小，且环不会影响答案的题目

题目：

[NOIP2018 提高组] 旅行

二次dp法

对于环，我们可以像环形dp一样将一条边强行断开处理，然后强行连上再处理一遍
适合：跑满足正确性的

题目：

ZJOI2008骑士

断环复制法

我们依旧像环形dp一样断开环，然后再复制一遍放在后面
适合：多个需要维护的

题目：

IOI2008 Island
AcWing 289. 环路运输