HDU 2818 Building Block

题目：Building Block

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2818

题意：

　　有 n 个元素，初始分成 n 堆（每堆一个），接下来有 p 个操作：

　　1. M x y　　：将下标为x 的元素所在的堆放在 y元素所在堆的上面

　　2. C x 　　：问下标为x 的元素下方有多少元素。

思路：

　　并查集的好题！！！

　　普通并查集一般是问集合内的元素个数，这题问的是集合内指定元素下方的元素个数。

　　这里，我用了三个数组，fa[]，son[]，unum[]，fa[x]表示x上方的元素，son[x]表示x下方的元素，unum[x]表示x下面的元素个数（包括x元素不包括son[x]下方的元素）。

　　假设我现在要将L堆放在R堆上面，那么son[C]就变成了D了，也就是L堆的最底层孩子的son值改为R堆祖先下标。这里的改变没必要更改各元素的unum属性，而在查询下方元素个数时，递归的同时要主意路径压缩。

AC代码：

 1 #include<stdio.h>
 2 #include<queue>
 3 using namespace std;
 4 #define N 30005
 5 
 6 int fa[N], son[N], unum[N];
 7 
 8 int find(int x)
 9 {
10   return fa[x]= fa[x]==x ? x : find(fa[x]);
11 }
12 
13 pair<int, int> findSon(int x)
14 {
15   if(son[x]==x) return make_pair(x, unum[x]);
16 
17   pair<int, int> ret = findSon(son[x]);
18   int child = ret.first;
19   int num = ret.second;
20 
21   unum[x] = unum[x] + num - unum[child];
22   son[x] = child;
23 
24   return make_pair(child, unum[x] + unum[child]);
25 }
26 
27 void mov(int x, int y)
28 {
29   int fx = find(x);
30   int fy = find(y);
31   if(fx==fy) return ;
32   else fa[fy]=fx;
33 
34   int sx = findSon(x).first;
35   son[sx] = fy;
36 }
37 
38 int main()
39 {
40   int m, x, y;
41   while(scanf("%d", &m)!=EOF)
42   {
43     for(int i=0; i<N; i++) fa[i]=i, son[i]=i, unum[i]=1;
44     while(m--)
45     {
46       char s[2];
47       scanf("%s", s);
48       if(s[0]=='M')
49       {
50         scanf("%d%d", &x, &y);
51         mov(x, y);
52       }
53       else
54       {
55         scanf("%d", &x);
56         printf("%d
", findSon(x).second-1);
57       }
58     }
59   }
60   return 0;
61 }