NC16466 [NOIP2015]信息传递 （带权并查集）

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

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

输入描述:
第 1 行包含 1 个正整数 n，表示 n 个人。
第 2 行包含 n 个用空格隔开的正整数T1,T2, … … ,Tn，其中第 i 个整数Ti表示编号为 i 的同学的信息传递对象是编号为Ti的同学，Ti≤ n 且Ti≠ i。

数据保证游戏一定会结束。

输出描述:
1个整数，表示游戏一共可以进行多少轮。
思路：
每个点的出度最多为1，这是这道题很重要的一个性质。
这就意味着其可以用拓扑来做。
不过这里用了并查集来做。
注意：
$在check()中，当x==y时，一定满足，(x==a)或(y==b)$。所以祖先一定在环上。这个题解也是应用了这个性质，否则不成立。
代码：

#include
using namespace std;
const int N=1e6+10;
int d[N],fa[N];
int res=0x3f3f3f3f;
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    else
    {
        int tmp=fa[x];
        fa[x]=find(fa[x]);
        d[x]+=d[tmp];
        return fa[x];
    }
}
void check(int a,int b)
{
    int x=find(a),y=find(b);
    if(x!=y)
    {
        fa[x]=y;
        d[a]=d[b]+1;
    }
    else
    {
        res=min(res,d[a]+d[b]+1);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        check(i,t);
    }
    cout<<res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48