hdu3635 Dragon Balls

题意：给你1~n个城市每个城市有一个球编号与城市编号相同，现在又两种操作1.T X Y 把x球所在城市的所有球转移到y球所在的城市。2.Q X 求出X球所在的城市编号 城市中球的总数 X球移动的次数

思路：这题明显的并查集，很好的一道题，其关键在于如何记录球移动次数。当一个球从一个城市移到另一个城市之后，那么“之后”被转移的次数就等于他的直接父节点的转移次数，而经过一次路径压缩之后，实际上他已经被接到根节点后面了，值得注意的一点是，当前，如果一个点是根节点，那么他的转移次数一定是0。

#include<iostream>
#include<algorithm>
#define MAXN 10000+10
using namespace std;
int f[MAXN],r[MAXN],num[MAXN],n;
void init()
{
    for(int i=0;i<=n;i++)
    {
        f[i]=i;r[i]=1;
        num[i]=0;
    }
}
int find(int x)
{
    if(x==f[x])
        return f[x];
    int t=find(f[x]);
    num[x]+=num[f[x]];//x的转移次数等于本身+直接父节点的转移次数
    f[x]=t;
    return f[x];
}
void Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
        return ;
    f[a]=b;
    num[a]++;
    r[b]+=r[a];
    r[a]=0;
}
int main()
{
    int T,cas=0,m,a,b;
    char str[2];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        init();
        printf("Case %d:\n",++cas);
        while(m--)
        {
            scanf("%s",str);
            if(str[0]=='T')
            {
                scanf("%d %d",&a,&b);
                Union(a,b);
            }
            else {
                scanf("%d",&a);
                int t=find(a);
                printf("%d %d %d\n",t,r[t],num[a]);
            }
        }
    }
    return 0;
}