ZZ并查集

原文出處：http://blog.sina.com.cn/s/blog_5ec05ef30100cp7f.html

作者：angela

所謂并查集，它是一個集合，這個集合的元素也是集合，他支援三種操作

MakeSet(x)，建立一個隻有一個元素x的集合X0，将這個集合放入并查集中；

FindSet(x)，在并查集中尋找一個元素S（注意并查集的元素S也是集合） ，滿足

x屬于S； Union(x,y)， 将并查集中的元素S1,S2合并，其中x屬于S1，y屬于S2。

下面說說并查集的實作，其實很簡單，用樹來實作。所有屬于同一集合的元素屬于

同一棵樹，這樣我們就可以用數根來表示一個集合，要找到某個元素屬于哪個集合

，隻要找到這個元素所在的樹的樹根；要合并兩個集合，隻要合并兩棵樹。一般比

較友善的方法是用父親數組Parent[]來表示樹，Parent[i]就是節點i的父結點，樹

根的父結點就是它本身。這樣很容易根據某個節點找到他的根，也很容易合并兩棵

樹。但是我們要考慮效率問題。在最壞的情況下，一棵樹退化成一個單連結清單（想象

一下所有的結點隻有唯一的兒子節點），這樣如果連結清單長度為L，從一個節點找到

他的根也需要L次運算，對于一共有n個節點元素的并查集，FindSet平均情況和最

壞情況下的複雜度都是O(n)，效率并不高。對于一棵樹而言，如果樹的高度為H，

那麽從葉節點隻要經過H次運算就可以找到樹根，是以我們應該盡量減少樹的高度

，最好的情況是樹的高度隻有1層，這樣就是一個樹根下面有很多兒子，這些兒子

都是樹葉。但是如果兩棵這樣的樹合并，數的高度就會增加，比如高度為H1的樹

T1和高度為H2的樹T2合并，得到的樹的高度有兩種情況： max { H1, H2+1}或者

max{H1+1, H2}，前一種情況是T2的根作為T1的根的兒子，後一種情況則是T1的根

作為T2的根的兒子。這就說明經過多次Union操作以後，樹的高度會增加。為了使

得樹的高度盡量地小，我們應該将較矮的樹合并到較高的樹上，是以我們用一個數

rank記錄每棵樹的高度，rank[i]就是以i為根的子樹的高度，在合并的時候就可以

根據rank的值進行合并，Union的代碼如下：

// 合并x,y所在的集合，并傳回交集

int Union(int x, int y)

{

x = FindSet( x ); // 找到x所在的樹的根

y = FindSet( y ); // 找到y所在的樹的根

if( x == y ) return x; // -1表示空集

if( x == -1 ) return y;

if( y == -1 ) return x;

if( Rank[x] > Rank[y] ) { // 将較低的樹合并到較高的樹上

Parent[y] = x;

return x;

}

else {

Parent[x] = y;

if( Rank[x] == Rank[y] ) Rank[y]++; // 改變樹的高度

return y;

}

}

Union其實是一種啟發式算法，rank[i]就是啟發函數值。

另外，為了降低樹的高度，我們在FindSet的時候也會壓縮路徑，比如原來a是樹根

，b是a的兒子，c是b的兒子，d是c的兒子，我們調用FindSet(d)找d所在的樹的樹

根，在找的同時，我們改變該樹的結構，使得調用FindSet(d)結束以後樹的結構變

為a是樹根，b是a的兒子，c也是a的兒子，d也是a的兒子。這就叫做路經壓縮。因

此FindSet代碼如下：

// 傳回到元素i所屬的集合的代表元素, 同時進行路徑壓縮

int FindSet(int i)

{

if( ( i == -1 ) || ( i >= CAPACITY ) ) { // -1表示空集

return -1;

}

else {

if( ( Parent[i] != -1 ) && ( Parent[i] != i ) )

Parent[i] = FindSet( Parent[i] ); // 這句話進行路徑壓縮

return Parent[i];

}

}

并查集的效率很高，可以證明，通過這種樹形結構實作的帶啟發式路徑壓縮的并查

集，FindSet和Union操作的平均代價是O(lgn)，這和二分查找的複雜度一緻，可以

證明這已經是理論上最好的算法了，不可能有更好的算法了。如果不進行這種路經

壓縮的話，并查集就退化成了連結清單，在同一連結清單中的元素屬于同一集合，這樣的話

FindSet的複雜度是O(n)。

并查集也是很常用的資料結構，有一道題目“親戚”，也要用并查集：

題目： 親戚(Relations)

　　或許你并不知道，你的某個朋友是你的親戚。他可能是你的曾祖父的外公的女

婿的外甥女的表姐的孫子。如果能得到完整的家譜，判斷兩個人是否親戚應該是可

行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那麼

檢驗親戚關系實非人力所能及。在這種情況下，最好的幫手就是計算機。

　　為了将問題簡化，你将得到一些親戚關系的資訊，如同Marry和Tom是親戚，

Tom和Ben是親戚，等等。從這些資訊中，你可以推出Marry和Ben是親戚。請寫一個

程式，對于我們的關于親戚關系的提問，以最快的速度給出答案。

　　參考輸入輸出格式 輸入由兩部分組成。

　　第一部分以N，M開始。N為問題涉及的人的個數(1 ≤ N ≤ 20000)。這些人的

編号為1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有兩個數ai, bi，表示

已知ai和bi是親戚。

　　第二部分以Q開始。以下Q行有Q個詢問(1 ≤ Q ≤ 1 000 000)，每行為ci,

di，表示詢問ci和di是否為親戚。

　　對于每個詢問ci, di，若ci和di為親戚，則輸出Yes，否則輸出No。

　　樣例輸入與輸出

輸入relation.in

10 7

2 4

5 7

1 3

8 9

1 2

5 6

2 3

3

3 4

7 10

8 9

輸出relation.out

Yes

No

Yes

如果這道題目不用并查集，而隻用連結清單或數組來存儲集合，那麼效率很低，肯定超

時。