【图论】环

更新于 分类于 ， 阅读次数： 本文字数： 526 阅读时长 ≈ 1 分钟

图论中的环相关内容

并查集求最小环（无向图，出度只能为1）：连一条由A指向B的边，更新B的父节点，A到它的父节点的路径长=B到它的父节点的路径长+1，如果有两个点祖先节点相同，那么就可以构成一个环，长度为两个点到祖先节点长度之和+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//luoguP2661
int father(int x)
{
    if(fa[x]==x) return x;
    int cur=fa[x]; //记录之前更新到的父亲节点
    int xf=father(fa[x]); //递归找父亲节点
    fa[x]=xf; //更新父亲节点
    cnt[x]+=cnt[cur]; 
    //如果没有更新到最顶上的父亲节点就会更新值
    //如果已经更新到最顶上，加的是0
    return xf;
}
void unite(int x,int y) //将x连到y，即x继承y的父亲节点
{
    int xf=father(x),yf=father(y);
    if(xf==yf)
        ans=min(ans,cnt[x]+cnt[y]+1); //这题求最小环，所以更新答案
    else
        fa[xf]=yf, cnt[x]=cnt[y]+1; //父亲节点+1
}

记忆化搜索求简单链+环