<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Disjoint Set - 并查集 -------- #### 描述 現在有一個擁有$$ n $$個成員的集合$$ s = [ x_0, x_1, x_2, \cdots , x_{n-1} ] $$，依次聲明$$ x_i $$和$$ x_j $$屬于或不屬于同一個家族，最終將所有成員分為兩個家庭。每個家族中只有唯一一個祖先，其余的成員必然有一個父親，遞歸的向上查找，除了祖先自己，其余每個成員所屬的祖先只有$$ 2 $$種可能。并查集是一種適合成員分類的高效樹形數據結構，支持快速分類和查詢。 設$$ father[x] $$為$$ x $$節點的父節點，當$$ father[x] = x $$時稱$$ x $$為祖先節點，它是家族中所有其他成員共同的唯一祖先，設$$ ancestor[x] $$是$$ x $$的祖先節點。 對于擁有$$ 10 $$個成員的集合$$ s = [ 0,1,2,3,4,5,6,7,8,9 ] $$，將其分成兩個家庭$$ A $$和$$ B $$。初始時令每個成員的父親都是自己，如圖所示：  當聲明$$ 2 $$個成員$$ x_i $$和$$ x_j $$（$$ x_i \le x_j $$）屬于同一家庭，直接令$$ x_i $$的節點祖先為$$ x_j $$的父親（也可以反過來），即$$ father[x_j] = ancestor[x_i] $$。這樣的操作會使元素$$ x_j $$的最接近祖先節點，從而縮短了遞歸向上查找的路徑長度，因此該操作也稱為壓縮路徑。 下面對上圖中的集合$$ s $$進行具體演示： $$ (1) $$聲明$$ 0 $$和$$ 4 $$屬于同一家庭，比較$$ 0 $$和$$ 4 $$的祖宗節點，設置$$ father[4] = ancestor[0] = 0 $$，本文中我們取左節點的祖宗節點作為右節點的父節點；  $$ (2) $$聲明$$ 1 $$和$$ 9 $$節點屬于同一家庭，設置$$ father[9] = ancestor[1] = 1 $$；  $$ (3) $$聲明$$ 0 $$和$$ 2 $$節點屬于同一家庭，設置$$ father[2] = ancestor[0] = 0 $$；  $$ (4) $$聲明$$ 1 $$和$$ 3 $$節點屬于同一家庭，設置$$ father[3] = ancestor[1] = 1 $$；  $$ (5) $$聲明$$ 3 $$和$$ 5 $$節點屬于同一家庭，設置$$ father[5] = ancestor[3] = 1 $$；  $$ (6) $$聲明$$ 6 $$和$$ 8 $$節點屬于同一家庭，設置$$ father[8] = ancestor[6] = 6 $$；  $$ (7) $$聲明$$ 2 $$和$$ 6 $$節點屬于同一家庭，設置$$ father[6] = ancestor[2] = 0 $$；  $$ (8) $$聲明$$ 1 $$和$$ 7 $$節點屬于同一家庭，設置$$ father[7] = ancestor[1] = 1 $$；  合并兩節點$$ x $$和$$ y $$時，根據固定規則設置$$ father[y] = ancestor[x] $$（或者相反）；查詢節點$$ x $$的祖宗節點時，若$$ father[x] \neq ancestor[x] $$則設置$$ father[x] = ancestor[x] $$。并查集的分類、查詢操作的時間復雜度接近$$ O(1) $$。 -------- #### 源碼 [DisjointSet.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/DisjointSet.h) [DisjointSet.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/DisjointSet.cpp) #### 測試 [DisjointSetTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/DisjointSetTest.cpp)