【带权并查集判环】信息传递

题意：一个接一个地传递消息，一个人只能传递给另一个人，但是可以接受到多个人传递过来的消息，问什么时候传递的消息出现回路？

题目分解： 判环的问题，形如 A->B->C->A 时，出现了环，此时游戏经过了三个箭头，答案是3。

思路：A->B，那么B玩家得到消息的祖先就是A，同理，B->C，c得到的消息的祖先也是A，此时A,B,C在同一个集合内。然后C->A，C的祖先是A，A的祖先也是A，代表此时出现了环，游戏结束，输出回合数。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;
int fa[N],d[N],n,ans=1999999999;
//d用来存距离祖先的距离，答案就是min(d[x]+d[y])。
//意思是祖先先走到x，然后从x走到y，然后从y走到祖先的距离
int f(int x)
{
  if( fa[x]!=x )
  {
    int p=fa[x];
    fa[x]=f(fa[x]);
    d[ x ]+=d[ p ];
  }
  return fa[x];
}
void check(int a,int b)
{
  int x=f(a),y=f(b);
  if( x!=y ) fa[a]=y,d[a]+=d[b]+1;
  else ans=min(ans,d[a]+d[b]+1);
}

int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    fa[i]=i;
  }
  int x,y;
  for(int i=1;i<=n;i++)
  {
    cin>>x;
    check(i,x);
  }
  cout<<ans;

}