題意是給出N個立方體，可以將立方體移動到其它立方體形成堆，然后有P個下面的操作: 1) M X Y ,將X立方體所在的堆移到Y(jié)立方體所在的堆的上面; 2) C X 輸出在X所在的堆上,在X立方體下面的立方體個數(shù)。
使用并查集來解決這個問題。關(guān)鍵在于怎么存儲和更新立方體的結(jié)果(即操作2的輸出值)。用三個數(shù)組，p,h,t, p[i]表示i的根結(jié)點，h[i]表示i的結(jié)果，即壓在i下面的立方體個數(shù)，t[i]表示i所在的堆的立方體總個數(shù)。對于每一堆立方體，根結(jié)點使用堆底的立方體，而且在這個堆所對應(yīng)的集合內(nèi)，通過更新，使得只有根結(jié)點的t值為這堆的總個數(shù)，h值為0(因為它在堆底)，其它的立方體的t值都為0，h值在并查集的查找步驟中進(jìn)行遞歸更新。
在并查集的查找函數(shù)的執(zhí)行中，先向上找到根結(jié)點，并且保存當(dāng)前結(jié)點x的父節(jié)點為temp，找到根結(jié)點后，向下依次一更新結(jié)點的h,t值。
1)若t[x]不為0,即表示x是一個堆的堆底元素，h[x]為0,其父節(jié)點是另外一堆的堆底(因為在并查集的操作中，通過將一個堆的堆底指向另一個堆的堆底來實現(xiàn)合并), h[x]+=t[temp],t[temp]+=t[x],t[x]=0 ，這三個語句將x的h值加上父結(jié)點的總個數(shù)(因為是將x所在的堆放在父節(jié)點的堆),然后將父節(jié)點的t值加上x的t值(父節(jié)點的堆的總數(shù)變?yōu)閮烧咧停缓笤賹的t值置0.
2)若t[x]為0,即表示x不是堆底，那么只要將x的h值加上父節(jié)點的h值即可。h[x]+=h[temp] 。
畫個圖然后稍微分析查找操作的過程就能得到上面的結(jié)果。下面是并查集的幾個函數(shù)。在合并操作里面，合并完后我們再對x,y執(zhí)行一次查找操作以更新對應(yīng)堆的值，因為在下次合并的時候可能堆還沒有來得及更新。
1 void make_set()
2 {
3 int i;
4 for(i=1;i<N;++i)
5 {
6 p[i]=i;
7 h[i]=0;
8 t[i]=1;
9 }
10 }
11 int find_set(int x)
12 {
13 int temp;
14 if(x!=p[x])
15 {
16 temp=p[x];
17 p[x]=find_set(p[x]);
18 if(t[x]!=0)
19 {
20 h[x]+=t[temp];
21 t[temp]+=t[x];
22 t[x]=0;
23 }else
24 {
25 h[x]+=h[temp];
26 }
27 }
28 return p[x];
29 }
30 void union_set(int x,int y)
31 {
32 int px=find_set(x),py=find_set(y);
33 p[px]=py;
34 find_set(x),find_set(y);
35 }
36