并查集
题目意思：
T a b 表示把a龙珠所在的城里的所有龙珠运到b所在的城里
Q a 表示对a的询问，要求输出 a所在的城， a所在的城里一共有多少个龙珠， a经过几次到达现在所在的城的。（移动的次数）
本题要点：
1、主要是记录移动次数：
其实每个根结点都是最多移动一次的，
所以记录移动次数把自己的加上父亲结点的就是移动总数了
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 10010;
int sum[MaxN];
int trans[MaxN]; //转换次数
int fa[MaxN];
int T, n, m;int get(int x)
{
if(fa[x] == x)return x;int tmp = fa[x];fa[x] = get(fa[x]);trans[x] += trans[tmp];return fa[x];
} void merge(int x, int y)
{
int fax = get(x);int fay = get(y);if(fax != fay){
fa[fax] = fay;sum[fay] += sum[fax];trans[fax] = 1;}
}void init()
{
for(int i = 1; i <= n; ++i){
fa[i] = i, sum[i] = 1, trans[i] = 0;}
}int main()
{
char ch[2];int x, y;scanf("%d", &T);for(int t = 1; t <= T; ++t){
scanf("%d%d", &n, &m);init();printf("Case %d:\n", t);for(int i = 0; i < m; ++i){
scanf("%s", ch);if(ch[0] == 'T'){
scanf("%d%d", &x, &y);merge(x, y);}else{
scanf("%d", &x);int y = get(x);printf("%d %d %d\n", y, sum[y], trans[x]);}}}return 0;
}/* 2 3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1 *//* Case 1: 2 3 0 Case 2: 2 2 1 3 3 2 */