POJ 1988 Cube Stacking

题意：有编号为1~N的N个小木块，有两种操作

M x y 将木块x所在的堆放到木块y所在的堆的上面
C x 询问木块x下面有多少块木块

代码巧妙就巧妙在GetParent函数中在进行路径压缩的同时，也计算好了该木块对应的under值

这个需要好好体会

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 30000 + 10;
 8 int parent[maxn], under[maxn], sum[maxn];
 9 
10 int GetParent(int a)
11 {
12     if(parent[a] == a)
13         return a;
14     int t = GetParent(parent[a]);
15     under[a] += under[parent[a]];
16     parent[a] = t;
17     return t;
18 }
19 
20 void Merge(int a, int b)
21 {
22     int pa = GetParent(a);
23     int pb = GetParent(b);
24     if(pa == pb)    return;
25     parent[pb] = pa;
26     under[pb] = sum[pa];
27     sum[pa] += sum[pb];
28 }
29 
30 int main(void)
31 {
32     #ifdef LOCAL
33         freopen("1988in.txt", "r", stdin);
34     #endif
35 
36     for(int i = 1; i < maxn; ++i)
37     {
38         parent[i] = i;
39         under[i] = 0;
40         sum[i] = 1;
41     }
42     int n;
43     scanf("%d", &n);
44     getchar();
45     for(int i = 0; i < n; ++i)
46     {
47         char p;
48         scanf("%c", &p);
49         if(p == 'M')
50         {
51             int a, b;
52             scanf("%d%d", &a, &b);
53             getchar(); 
54             Merge(b, a);
55         }
56         else
57         {
58             int a;
59             scanf("%d", &a);
60             getchar();
61             GetParent(a);
62             printf("%d
", under[a]);
63         }
64     }
65     return 0;
66 }

代码君