1 /* 2    题意：有N个城市， 每一个城市都有一个龙珠（编号与城市的编号相同），有两个操作 3    T A ,B 将标号为A龙珠所在城市的所有的龙珠移动到B龙珠所在城市中！  4     5    思路：并查集 （压缩路径的时候将龙珠移动的次数进行更新）  6 */ 7 #include<iostream>  8 #include<cstring> 9 #include<cstdio>10 #include<algorithm>11 #define M 1000512 using namespace std;13 14 int f[M];//表示龙珠 i 所在的城市标号 15 int Tcnt[M];//记录每个龙珠移动的次数 16 int Scnt[M];//记录每个城市中龙珠总个数 17 18 int getFather(int x){19    if(x==f[x])20      return x;21    22    int ff=getFather(f[x]); 23    Tcnt[x]+=Tcnt[f[x]];//每一个龙珠移动的次数+=其依附的父亲龙珠移动的次数 24    f[x]=ff;25    return f[x]; 26 }27 28 void Union(int a, int b){29    int fa=getFather(a);30    int fb=getFather(b);31    if(fa==fb) return;32    f[fa]=fb;33    Scnt[fb]+=Scnt[fa];//将fa城市的龙珠全部移动到fb城市中！ 34    Scnt[fa]=0;35    Tcnt[fa]+=1;//a球移动次数+1 36 } 37 38 int main(){39    int t, a, b;40    int n, m;41    char ch[2];42    scanf("%d", &t);43    for(int cc=1; cc<=t; ++cc){44           printf("Case %d:\n", cc); 45        scanf("%d%d", &n, &m);46        memset(Tcnt, 0, sizeof(int)*(n+1));47        for(int i=1; i<=n; ++i)48           f[i]=i, Scnt[i]=1;49        while(m--){50           scanf("%s", ch);51           if(ch[0]==‘T‘){52              scanf("%d%d", &a, &b);53              Union(a, b); 54           }55           else {56              scanf("%d", &a);57              int ff = getFather(a);58              printf("%d %d %d\n", ff, Scnt[ff], Tcnt[a]); 59           }          60        }61    } 62    return 0;63 }