//// main.cpp// 5.1.6//// Created by Fangpin on 15/3/2.// Copyright (c) 2015年 Fangpin. All rights reserved.//#include <iostream>#include <cstring>using namespace std;int set[10003],sum[10003],times[10003];int find(int x){if(x==set[x])return x;else{int tem=set[x];set[x]=find(set[x]);times[x]+=times[tem];}return set[x];}int main(int argc, const char * argv[]) {// insert code here…int t,n,q;scanf("%d",&t);for(int ca=1;ca<=t;++ca){scanf("%d%d",&n,&q);for(int i=0;i<=n;++i){set[i]=i;sum[i]=1;times[i]=0;}printf("Case %d:\n",ca);while(q–){char s[5];scanf("%s",s);if(s[0]=='T'){int a,b;scanf("%d%d",&a,&b);int fa=find(a),fb=find(b);if(fa!=fb){set[fa]=fb;times[fa]++;sum[fb]+=sum[fa];sum[fa]=0;}}else{int a;scanf("%d",&a);int fa=find(a);printf("%d %d %d\n",fa,sum[fa],times[a]);}}}return 0;}并查集的运用，每次合并的时候注意多加一个记录元素个数的域。
本题较难的是第三个问题。容易发现，如果不加优化的话，该球被移动的次数恰是该数所在数的树中位置的节点深度。但为了减少时间复杂度，避免退化树的出现，应该加入路径压缩。
，留下许多叫知识和情感的东西握在手里。
