洛谷p2661信息传递

题目：##

有 n 个同学（编号为 1到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti​ 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

题目链接：信息传递

分析：###

昂 有向边？跑tarjan？
刚刚做了两道并查集的我偷偷看了一眼标签准备用并查集再水一道题（tarjan好长啊果断并查集大法好啊（……）
当一个人的生日被传回来的时候说明出现了环，这个题目很显然要求的是最小环，游戏结束的轮数就是最小环的长度
裴成环，坚成环，裴坚……咳
可以考虑用并查集维护这个过程，每读入一个数据，先检查这两点是否已经连通（成环），若已经成环则更新最小值（最小值=两个节点分别到祖先的距离+1（这个1指这两个节点之间连的一条边）），若没有成环则连一条边，设这条边是A→B的有向边，那么显然有A到祖先节点的距离=B到祖先节点的距离+1
更新father的过程中，记录一个当前搜索到的x的父节点last，先走上去到x的最老的祖先节点，边走边路径压缩，然后回溯回来的时候把值一层层传递下来

---

放一下代码吧（其实特别短来着）：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int cnt=0,f=1;char c;
    c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-f;
        c=getchar();
    }
    while(isdigit(c)){
        cnt=cnt*10+c-'0';
        c=getchar();
    }
    return cnt*f;
}
int n;
int t;
int fa[200005],d[200005];
int minn=1<<20;

int get_father(int x){
    if(fa[x]!=x){
        int last=fa[x];
        fa[x]=get_father(fa[x]);
        d[x]+=d[last];
    }
    return fa[x];
}
void check(int a,int b){
    int x=get_father(a);
    int y=get_father(b);
    if(x!=y){fa[x]=y;d[a]=d[b]+1;}
    else minn=min(minn,d[a]+d[b]+1);
    return ;
}
int main(){
    n=read();
    for(register int i=1;i<=n;i++)fa[i]=i,d[i]=0;
    for(register int i=1;i<=n;i++){
        t=read();
        check(i,t);
    }
    printf("%d",minn);
    return 0;
}

参考了一下洛谷第一篇题解&&神犇fsy博客，真的是很神仙的思路诶，比tarjan又好写又巧妙才不是因为我懒