HDU 3635 Dragon Balls（带权并查集）

http://acm.hdu.edu.cn/showproblem.php?pid=3635

题意：

有n颗龙珠和n座城市，一开始第i颗龙珠就位于第i座城市，现在有2种操作，第一种操作是将x龙珠所在城市的所有龙珠移至y龙珠所在城市，第二种操作是计算x龙珠所在城市y，y城市龙珠个数，以及x龙珠移动的次数。

思路：
num[x]用来维护x城市所包含的龙珠个数，cnt[x]维护x龙珠所移动的次数。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = +;

 int n, m;

 int p[maxn], num[maxn], cnt[maxn];

 int finds(int x)

 {

     if(p[x]==x)  return x;

     int tmp=p[x];

     p[x]=finds(p[x]);

     cnt[x]+=cnt[tmp];

     return p[x];

 }

 int main()

 {

    //freopen("in.txt","r",stdin);

    int T;

    int kase = ;

    scanf("%d",&T);

    while(T--)

    {

        printf("Case %d:\n",++kase);

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)  {p[i]=i;num[i]=;cnt[i]=;}

        while(m--)

        {

            char op[];

            scanf("%s",op);

            if(op[]=='T')

            {

                int x,y;

                scanf("%d%d",&x,&y);

                int xx = finds(x);

                int yy = finds(y);

                if(xx!=yy)

                {

                    p[xx]=yy;

                    cnt[xx]++;

                    num[yy]+=num[xx];

                    num[xx]=;

                }

            }

            else

            {

                int x;

                scanf("%d",&x);

                int ans = finds(x);

                printf("%d %d %d\n",ans,num[ans],cnt[x]);

            }

        }

    }

    return ;

 }