并查集

在一些應用問題中，需要將n個不同的元素劃分成一些不相交的集合。開始時，每個元素自成一個集合，然后按照一定的規律將歸于同一組的元素集合合并。在此過程中要反復用到查詢某一個元素歸屬于哪一個集合的運算。適合于描述這類問題的抽象數據結構類型成為并查集（UnionFindSet）。

比如：親戚關系，朋友敵人關系，食物鏈關系。

比如：給定10個人，5對關系，沒對關系描述兩個人，表示這兩個人是親戚，最后問你某兩個人之間是否是親戚關系。

再比如：給定10個人，5對關系，沒對關系描述兩個人，表示這兩個人之間的關系（朋友或者敵人），最后問你某兩個人之間的關系。

…………

上述問題就可以使用并查集這一數據結構來解決。

接下來實現并查集這一數據結構

以一個簡單的列子為例：

某公司今年校招全國總共招生10人，西安招4人，成都招3人，武漢招3人，10個人來自不

同的學校，起先互不相識，每個學生都是一個獨立的小團體，現給這些學生進行編號：{0, 1, 2, 3,

4, 5, 6, 7, 8, 9}; 給以下數組用來存儲該小集體，數組中的數字代表：該小集體中具有成員的個

數。(負號下文解釋)

畢業后，學生們要去公司上班，每個地方的學生自發組織成小分隊一起上路，于是：

西安學生小分隊s1={0,6,7,8}，成都學生小分隊s2={1,4,9}，武漢學生小分隊s3={2,3,5}就相互認識

了，10個人形成了三個小團體。假設右三個群主0,1,2擔任隊長，負責大家的出行。

一：初始化

起初時，我們可以創建一個數組，數組下標表示元素的編號，數組中的值全部初始化為-1，表示該元素最初子集單獨為一個集合（自己就是父親）。

二：Find操作

該操作的目的是判斷某個元素屬于哪個集合（找到該元素所屬集合的代表元素（通俗來說就是向上找跟操作））。

該操作可以通過循環來實現，不斷去找自己的父親，不斷向上走，知道最終的元素沒有父親（值為-1）為止。

三：Union操作

已知兩個元素之間存在關系要合并這兩個元素，本質是將這兩個元素所屬的集合進行合并，這很好理解，朋友的朋友還是朋友。因此要先進行找兩個元素所屬集合的根節點，最終將這兩個集合合并（一個集合的根節點認另一個集合的根節點為父親）

順便可以統計一下合并后集合共有多少元素（abs(_ufs[root1])）

四：ISsame操作

給定兩個元素，判斷這兩個元素是否屬于同一個集合。

只需要判斷這兩個集合的祖先是否相同就可以了。

五：SetCount操作

判斷當前一共有多少個集合（有多少個大家庭）

只需要遍歷一遍數組，判斷有多少值為-1就可以了。

并查集優化操作

一般來說并查集實現成上面的樣子已經可以了，但是當數據量比較龐大的時候，效率（性能）

就會有所下降，因此要考慮進行優化。

一：優化Union操作

在上面實現的并查集中，采用的方法是將下標大的元素向下標小的元素合并，極端情況下經過一系列合并后集合會成為一個鏈表結構（一條線），再進行Find操作時時間復雜度就會是O(n)。

因此，我們改變合并思路，我們每次進行合并操作時，都將元素數量少的集合向元素數量多的集合合并，這樣就可以很好的控制集合這一樹形結構的高度，性能就會有所提升。

二：路徑壓縮

并查集只是要在某一個集合中找出一個代表元素，并不在意找出哪一個，因此對于不是根的結點，

認誰為父親都是可以的，因此我們在Find操作的過程中就可以進行路徑壓縮，將所有遍歷到的結點

的父親都修改成root，這樣可以大大降低樹的高度，查找的時間復雜度近似為O(1),性能就會提升。

路徑壓縮也可以實現成遞歸的形式（代碼短，好寫），但是不太推薦，遞歸怕的就是層數太深，

如果數據量非常大的情況下遞歸很可能是不可行的。