【题解】洛谷P2661 [NOIP2015TG] 信息传递

题目来源：洛谷P2661

思路

运用并查集查找图中最小环的长度

如果A传递信息给B 就从A加一条边指向B 并更新A的父节点 从A到父节点的路径长度为B到父节点的路径长度+1

如果有两个点的祖先相同而且他们之中有一个人要传递信息给另一个人

那么说明他们之间有一个环 环的长度就是他们分别到祖先的路径长之和+1

代码

#include<iostream>
using namespace std;
#define maxn 200020
int fa[maxn],lun[maxn];
int n,ans=1e9+7;
int find(int x)
{
    if(fa[x]!=x)//查找时更新祖先和路径长度 
    {
        int temp=fa[x];//记录父节点（父节点会在递归过程中更新） 
        fa[x]=find(fa[x]);
        lun[x]+=lun[temp];//路径增加（连在最初的父节点上） 
    }
    return fa[x];    
}
void unionn(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a!=b)//如果祖先不同 
    {
        fa[a]=b;//更新a的祖先为b的祖先 
        lun[x]=lun[y]+1;//路径长度+1 
    }
    if(a==b)//如果祖先相同 
    ans=min(ans,lun[x]+lun[y]+1);//取最小值 
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) fa[i]=i;//初始化 
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        unionn(i,x);//加边 
    }
    cout<<ans;
}