洛谷p2661信息传递 题解

#include<cstdio>

#include<iostream>

using namespace std;

int f[200002],d[200002],n,minn,last;    d数组用来计数

int fa(int x)

{//升级版找爹函数

    if (f[x]!=x)                    

    {

        int last=f[x];                 

        f[x]=fa(f[x]);                  

        d[x]+=d[last];//计数                  

    }

    return f[x];

}

void Violentsearch(int a,int b)//升级版合并函数

{

    int x=fa(a),y=fa(b);                

    if (x!=y) {f[x]=y; d[a]=d[b]+1;}    

    else minn=min(minn,d[a]+d[b]+1);    

    return;

}

int main()

{

    int i,t;

    cin>>n;

    for (i=1;i<=n;i++) f[i]=i;          

    minn=2147483647;

    for (i=1;i<=n;i++)

    {

        cin>>t;

        Violentsearch(i,t);                    

    }

    cout<<minn;

    return 0;

}