1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXN 10000
 6 
 7 int father[MAXN + 1], trans[MAXN + 1], sum[MAXN + 1];
 8 
 9 void init_set(int n) {
10     for (int i = 1; i <= n; ++i) {
11         father[i] = i;
12         trans[i] = 0;
13         sum[i] = 1;
14     }
15 }
16 
17 int find_set(int x) {
18     int sx = x, ts = 0;
19     while (sx != father[sx]) {
20         ts += trans[sx];
21         sx = father[sx];
22     }
23     int t;
24     while (x != sx) {
25         ts -= trans[x];
26         trans[x] += ts;
27         t = father[x];
28         father[x] = sx;
29         x = t;
30     }
31     return sx;
32 }
33 
34 void union_set(int x, int y) {        // x to y
35     x = find_set(x); y = find_set(y);
36     father[x] = y;
37     trans[x] = 1;
38     sum[y] += sum[x];
39 }
40 
41 int main() {
42 #ifndef ONLINE_JUDGE
43     freopen("in.txt", "r", stdin);
44     freopen("out.txt", "w", stdout);
45 #endif
46     int test;
47     scanf("%d", &test);
48     for (int cas = 1; cas <= test; ++cas) {
49         int n, q;
50         scanf("%d%d", &n, &q);
51         printf("Case %d:\n", cas);
52         init_set(n);
53         for (int i = 0; i < q; ++i) {
54             char c; int a, b;
55             scanf(" %c", &c);
56             if (c == 'T') {
57                 scanf("%d%d", &a, &b);
58                 union_set(a, b);
59             } else {
60                 scanf("%d", &a);
61                 b = find_set(a);
62                 printf("%d %d %d\n", b, sum[b], trans[a]);
63             }
64         }
65     }
66     return 0;
67 }

xpycc 2010-09-24 09:19 发表评论