路径压缩

将每个节点直接与其get操作最终得到的节点链接，就是所谓的路径压缩。
通过路径压缩，我们可以提高查找效率。

代码

int get(int x)
{
    if(x==father[x]) return x;
    return father[x]=get(father[x]);
}

带权并查集

节点与节点之间有距离
基于路径压缩，带权并查集的构造时，权值的更新操作如下

代码

int get(int x)
{
    if(x==father[x]) return x;
    int y=father[x];
    fa[x]=get(y);
    dist[x]+=dist[y];
    return father[x];
}

本题思路

那么回归本题，本题所要求就是什么时候自己传出去的信息传回来
而传递信息就是连边，所以等价于求最小的成环长
我们可以看做从该点传到信息传递对象，由信息传递对象传给它们的公共父亲，再传回成环
//同学1 --> 同学2(同学1和同学2是好朋友,进行信息的传递) --> 同学X(公共父节点) --> 同学1(同学1突然震惊(ΩДΩ))
那么并查集恰好完美地解决了这个问题
我们用带权并查集求出点和信息传递对象到公共父节点距离，进而求出点到信息传递对象的距离，就求得了成环的距离
然后循环更新最小成环距离即可

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=200000+10;
int n,t,ans=1000000007;
int fa[N],dist[N];
//dis存储的是点到父亲节点的距离
int get(int x)
{
    if(x==fa[x]) return x;
    int y=fa[x];
    fa[x]=get(y);
    dist[x]+=dist[y];
    return fa[x];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        int x=get(i),y=get(t);
        if(x!=y)    //父亲节点不相同
        {
            fa[x]=y;
            dist[i]=dist[t]+1;    //更新权值
        }
        else ans=min(ans,dist[i]+dist[t]+1);
        //如果已有公共父亲，直接求成环距离
        //成环距离就是点到父亲节点距离，加上父亲节点到信息传递对象距离，加一
    }
    printf("%d",ans);
    return 0;
}