/*
题意：有N个城市， 每一个城市都有一个龙珠（编号与城市的编号相同），有两个操作
T A ,B 将标号为A龙珠所在城市的所有的龙珠移动到B龙珠所在城市中！
思路：并查集 （压缩路径的时候将龙珠移动的次数进行更新）
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define M 10005
using namespace std;
int f[M];//表示龙珠 i 所在的城市标号
int Tcnt[M];//记录每个龙珠移动的次数
int Scnt[M];//记录每个城市中龙珠总个数
int getFather(int x){
if(x==f[x])
return x;
int ff=getFather(f[x]);
Tcnt[x]+=Tcnt[f[x]];//每一个龙珠移动的次数+=其依附的父亲龙珠移动的次数
f[x]=ff;
return f[x];
}
void Union(int a, int b){
int fa=getFather(a);
int fb=getFather(b);
if(fa==fb) return;
f[fa]=fb;
Scnt[fb]+=Scnt[fa];//将fa城市的龙珠全部移动到fb城市中！
Scnt[fa]=0;
Tcnt[fa]+=1;//a球移动次数+1
}
int main(){
int t, a, b;
int n, m;
char ch[2];
scanf("%d", &t);
for(int cc=1; cc<=t; ++cc){
printf("Case %d:\n", cc);
scanf("%d%d", &n, &m);
memset(Tcnt, 0, sizeof(int)*(n+1));
for(int i=1; i<=n; ++i)
f[i]=i, Scnt[i]=1;
while(m--){
scanf("%s", ch);
if(ch[0]=='T'){
scanf("%d%d", &a, &b);
Union(a, b);
}
else {
scanf("%d", &a);
int ff = getFather(a);
printf("%d %d %d\n", ff, Scnt[ff], Tcnt[a]);
}
}
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3902119.html，如需转载请自行联系原作者
