題意是給出N個(gè)立方體，可以將立方體移動(dòng)到其它立方體形成堆，然后有P個(gè)下面的操作: 1) M X Y ,將X立方體所在的堆移到Y(jié)立方體所在的堆的上面; 2) C X 輸出在X所在的堆上,在X立方體下面的立方體個(gè)數(shù)。
使用并查集來(lái)解決這個(gè)問(wèn)題。關(guān)鍵在于怎么存儲(chǔ)和更新立方體的結(jié)果(即操作2的輸出值)。用三個(gè)數(shù)組，p,h,t, p[i]表示i的根結(jié)點(diǎn)，h[i]表示i的結(jié)果，即壓在i下面的立方體個(gè)數(shù)，t[i]表示i所在的堆的立方體總個(gè)數(shù)。對(duì)于每一堆立方體，根結(jié)點(diǎn)使用堆底的立方體，而且在這個(gè)堆所對(duì)應(yīng)的集合內(nèi)，通過(guò)更新，使得只有根結(jié)點(diǎn)的t值為這堆的總個(gè)數(shù)，h值為0(因?yàn)樗诙训?，其它的立方體的t值都為0，h值在并查集的查找步驟中進(jìn)行遞歸更新。
在并查集的查找函數(shù)的執(zhí)行中，先向上找到根結(jié)點(diǎn)，并且保存當(dāng)前結(jié)點(diǎn)x的父節(jié)點(diǎn)為temp，找到根結(jié)點(diǎn)后，向下依次一更新結(jié)點(diǎn)的h,t值。
1)若t[x]不為0,即表示x是一個(gè)堆的堆底元素，h[x]為0,其父節(jié)點(diǎn)是另外一堆的堆底(因?yàn)樵诓⒉榧牟僮髦校ㄟ^(guò)將一個(gè)堆的堆底指向另一個(gè)堆的堆底來(lái)實(shí)現(xiàn)合并), h[x]+=t[temp],t[temp]+=t[x],t[x]=0 ，這三個(gè)語(yǔ)句將x的h值加上父結(jié)點(diǎn)的總個(gè)數(shù)(因?yàn)槭菍所在的堆放在父節(jié)點(diǎn)的堆),然后將父節(jié)點(diǎn)的t值加上x的t值(父節(jié)點(diǎn)的堆的總數(shù)變?yōu)閮烧咧停缓笤賹的t值置0.
2)若t[x]為0,即表示x不是堆底，那么只要將x的h值加上父節(jié)點(diǎn)的h值即可。h[x]+=h[temp] 。
畫個(gè)圖然后稍微分析查找操作的過(guò)程就能得到上面的結(jié)果。下面是并查集的幾個(gè)函數(shù)。在合并操作里面，合并完后我們?cè)賹?duì)x,y執(zhí)行一次查找操作以更新對(duì)應(yīng)堆的值，因?yàn)樵谙麓魏喜⒌臅r(shí)候可能堆還沒(méi)有來(lái)得及更新。
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