并查集砚亭，在一些有N個(gè)元素的集合應(yīng)用問題中褒墨，我們通常是在開始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合废登，然后按一定順序?qū)儆谕唤M的元素所在的集合合并震贵，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中利赋。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題猩系。常常在使用中以森林來表示媚送。
如下幾個(gè)概念：
1.集合樹：所有節(jié)點(diǎn)以代表節(jié)點(diǎn)為父節(jié)點(diǎn)構(gòu)成的多叉樹
2.節(jié)點(diǎn)的代表節(jié)點(diǎn)：可以理解為節(jié)點(diǎn)的父節(jié)點(diǎn)，從當(dāng)前節(jié)點(diǎn)出發(fā)寇甸，可以向上找到的第一個(gè)節(jié)點(diǎn)
3.集合的代表節(jié)點(diǎn)：可以理解為根節(jié)點(diǎn)塘偎，意味著該集合內(nèi)所有節(jié)點(diǎn)向上走，最終都能到達(dá)的節(jié)點(diǎn)
合并和查詢操作
合并（Union）：把兩個(gè)不相交的集合合并為一個(gè)集合
查詢（Find）：查詢兩個(gè)元素是否在同一個(gè)集合中
class UnionFindSet:
def UnionFindSet(n):
parents = [0,1...n] # 記錄每個(gè)元素的parent即根節(jié)點(diǎn) 先將它們的父節(jié)點(diǎn)設(shè)為自己
ranks =[0,0...0] # 記錄節(jié)點(diǎn)的rank值
# 如下圖 遞歸版本 路徑壓縮(Path Compression)
# 如果當(dāng)前的x不是其父節(jié)點(diǎn)拿霉，就找到當(dāng)前x的父節(jié)點(diǎn)的根節(jié)點(diǎn)(find(parents[x])) 并將這個(gè)值賦值給x的父節(jié)點(diǎn)
def find(x):
if ( x !=parents[x]): # 這里會(huì)同步更新該集合中所有的節(jié)點(diǎn)的代表節(jié)點(diǎn)
parents[x] = find(parents[x])
return parents[x]
# 如下圖 根據(jù)Rank來合并(Union by Rank)
def union(x,y):
rootX = find(x) # 找到x的根節(jié)點(diǎn)rootX
rootY = find(y) # 找到y(tǒng)的根節(jié)點(diǎn)rootY
#取rank值小的那個(gè)掛到大的那個(gè)節(jié)點(diǎn)下面吟秩，此時(shí)兩個(gè)根節(jié)點(diǎn)的rank值并沒有發(fā)生變化样勃，還是原來的值
if(ranks[rootX]>ranks[rootY]): parents[rootY] = rootX
if(ranks[rootX]<ranks[rootY]): parents[rootX] = rootY
# 當(dāng)兩個(gè)rank值相等時(shí)举畸，隨便選擇一個(gè)根節(jié)點(diǎn)掛到另外一個(gè)跟節(jié)點(diǎn)上，但是被掛的那個(gè)根節(jié)點(diǎn)的rank值需要+1
if(ranks[rootX] == ranks[rootY] ):
parents[rootY] = rootX
ranks[rootX]++
來源：
