记录移动次数，其实每个根结点都是最多移动一次的，所以记录移动次数把自己的加上父亲结点的就是移动总数
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 10010; 7 int fa[maxn]; 8 int num[maxn]; 9 int Move[maxn]; 10 11 int n; 12 13 void init() 14 { 15 for (int i = 1; i <= n; i++) 16 { 17 fa[i] = -1; 18 num[i] = 1; 19 Move[i] = 0; 20 } 21 } 22 23 int find(int x) 24 { 25 if (fa[x] == -1)return x; 26 int t = fa[x]; 27 fa[x] = find(fa[x]); 28 Move[x] += Move[t]; 29 return fa[x]; 30 } 31 32 void bing(int a, int b) 33 { 34 int t1 = find(a); 35 int t2 = find(b); 36 if (t1 != t2) 37 { 38 fa[t1] = t2; 39 num[t2] += num[t1]; 40 Move[t1] = 1; 41 } 42 } 43 44 int main() 45 { 46 int m; 47 int T; 48 char str[10]; 49 int a, b; 50 int iCase = 0; 51 scanf("%d", &T); 52 while (T--) 53 { 54 iCase++; 55 scanf("%d%d", &n, &m); 56 init(); 57 printf("Case %d: ", iCase); 58 while (m--) 59 { 60 scanf("%s", str); 61 if (str[0] == 'T') 62 { 63 scanf("%d%d", &a, &b); 64 bing(a, b); 65 } 66 else 67 { 68 scanf("%d", &a); 69 int t = find(a); 70 printf("%d %d %d ", t, num[t], Move[a]); 71 } 72 } 73 } 74 return 0; 75 }