並查集的定義

給定n個結點的集合，結點編號為1～n，再給定一個等價關係，由等價關係產生所有結點的一個劃分，每個結點屬於一個等價類，所有等價類是不相交的。

需要求一個結點所屬的等價類，以及合併兩個等價類。

並查集的實現

· 並查集就是一個森林。

· 每個等價類用一棵樹表示，包含該等價類的所有結點，即結點子集，

· 每個子集透過一個代表來識別，代表即該子集中的某個結點，通常選擇根做這個代表。

問題描述：如果已經得到完整的家譜，判斷兩個人是否親戚應該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那麼檢驗親戚關係就十分複雜。在這種情況下，就需要應用並查集。

為了將問題簡化，將得到一些親戚關係的資訊，如Marry和Tom是親戚，Tom和Ben是親戚，等等。從這些資訊中，可以推出Marry和Ben是親戚。

用有根樹來表示集合，樹中的每個結點包含集合的一個成員，每棵樹表示一個集合。

多個集合形成一個森林，以每棵樹的樹根作為集合的代表，並且根結點的父結點指向其自身，樹上的其他結點都用一個父指標表示它的附屬關係。

在並查集中，每個分離集合對應的一棵樹，稱為分離集合樹。整個並查集也就是一棵分離集合森林。

4個集合{1，2，3，4}、{5，6，7}、{8，9}、{10}，分別以4、7、9和10表示對應集合的編號。

查詢x

查詢x所在的子集

合併過程

查詢中的路徑壓縮

並查集的基本儲存結構（實際上是森林的雙親儲存結構）如下：

並查集的基本運算演算法

時間複雜度為O(n)。

用迭代方式實現

HDU1232—暢通工程問題。

問題描述：某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府"暢通工程"的目標是使全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接透過道路可達即可）。問最少還需要建設多少條道路？

輸入格式：測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數，分別是城鎮數目N（N<1000）和道路數目M，隨後的M行對應M條道路，每行給出一對正整數，分別是該條道路直接連通的兩個城鎮的編號。為簡單起見，城鎮從1到N編號。注意兩個城市之間可以有多條道路相通，也就是說：

3 3

1 2

1 2

2 1

這種輸入也是合法的。當N為0時，輸入結束，該用例不被處理。

· 要使全省任何兩個城鎮間都實現交通，最少的道路是所有城鎮之間都有一條路徑，即全部城鎮構成一棵樹。

· 採用並查集求解，由輸入構造並查集，每棵子樹中的所有城鎮是有路徑的，求出其中子樹的個數ans，那麼最少還需要建設的道路數就是ans-1。