hdu 3635 Dragon Balls (MFSet)

　　切切水题，并查集。

　　记录当前根树的结点个数，记录每个结点相对根结点的转移次数。1y~

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 const int N = 11111;
 8 struct MFS {
 9     int fa[N], tm[N], cnt[N];
10     void init() { for (int i = 0; i < N; i++) fa[i] = i, tm[i] = 0, cnt[i] = 1;}
11     int find(int x, int &t) {
12         if (fa[x] == x) {
13             t = 0;
14         } else {
15             fa[x] = find(fa[x], t);
16             tm[x] += t;
17             t = tm[x];
18         }
19         return fa[x];
20     }
21     void merge(int x, int y) {
22         int tmp;
23         int fx = find(x, tmp);
24         int fy = find(y, tmp);
25         tm[fy] -= tm[fx] - 1;
26         cnt[fx] += cnt[fy];
27         fa[fy] = fa[fx];
28 //        for (int i = 0; i < 5; i++) cout << fa[i] << ' '; cout << endl;
29     }
30     void query(int x) {
31         int tmp;
32         int fx = find(x, tmp);
33         printf("%d %d %d
", fx, cnt[fx], tm[x] + tm[fx]);
34     }
35 } mfs;
36 
37 int main() {
38     int T, n, m;
39     scanf("%d", &T);
40     for (int cas = 1; cas <= T; cas++) {
41         scanf("%d%d", &n, &m);
42         mfs.init();
43         char op[2];
44         int x, y;
45         printf("Case %d:
", cas);
46         for (int i = 0; i < m; i++) {
47             scanf("%s", op);
48             if (op[0] == 'T') {
49                 scanf("%d%d", &x, &y);
50                 mfs.merge(y, x);
51             } else {
52                 scanf("%d", &x);
53                 mfs.query(x);
54             }
55         }
56     }
57     return 0;
58 }

View Code

——written by Lyon