(本來(lái)想寫個(gè)并查集的文章灯帮，發(fā)現(xiàn)這一篇寫得很好琅绅，就直接摘抄過(guò)來(lái)了召川，也做個(gè)記錄【union-find】霞丧。
1. 概述
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)科吭，用于處理一些不交集（Disjoint Sets）的合并及查詢問(wèn)題。有一個(gè)聯(lián)合-查找算法（Union-find Algorithm）定義了兩個(gè)用于此數(shù)據(jù)結(jié)構(gòu)的操作：
find：確定元素屬于哪一個(gè)子集浑此。它可以被用來(lái)確定兩個(gè)元素是否屬于同一子集累颂。
union：將兩個(gè)子集合并成同一個(gè)集合滞详。
初始化每一個(gè)點(diǎn)都是一個(gè)連通域凛俱，類似下圖：
由于支持這兩種操作，一個(gè)不相交集也常被稱為聯(lián)合-查找數(shù)據(jù)結(jié)構(gòu)（Union-find Data Structure）或合并-查找集合（Merge-find Set）料饥。為了更加精確的定義這些方法蒲犬，需要定義如何表示集合。一種常用的策略是為每個(gè)集合選定一個(gè)固定的元素岸啡，稱為代表原叮，以表示整個(gè)集合。接著巡蘸，find(x) 返回 x 所屬集合的代表奋隶，而 union 使用兩個(gè)集合的代表作為參數(shù)。
2. 核心API
2.1 find
def find(self, x):
# 未進(jìn)行路徑壓縮
while x != self.parent[x]:
x = self.parent[x]
return x
比如下面這個(gè)圖悦荒，調(diào)用 find(0) 會(huì)逐步找到 3 唯欣。
若采用路徑壓縮方法，在找到 3 的過(guò)程上會(huì)將路徑上的節(jié)點(diǎn)都指向根節(jié)點(diǎn)搬味。
def find(self, x):
"""
查找節(jié)點(diǎn)的父(根)節(jié)點(diǎn)
"""
if x != self.parent[x]:
# 進(jìn)行了路徑壓縮
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
極限情況下境氢，每一個(gè)路徑都會(huì)被壓縮蟀拷，這種情況下繼續(xù)查找的時(shí)間復(fù)雜度就是 。
2.2 union
將其中一個(gè)節(jié)點(diǎn)掛到另外一個(gè)節(jié)點(diǎn)的祖先上萍聊，這樣兩者祖先就一樣了问芬。也就是說(shuō)，兩個(gè)節(jié)點(diǎn)聯(lián)通了寿桨。
對(duì)于如下的一個(gè)圖：
圖中 r:1 表示 秩為 1此衅，r 是 rank 的簡(jiǎn)寫。記錄以該結(jié)點(diǎn)為根結(jié)點(diǎn)的樹的深度牛隅。
def union(self, x, y):
"""
合并兩個(gè)節(jié)點(diǎn)炕柔，小的樹掛到大的樹上，使樹盡量平衡
"""
p, q = self.find(x), self.find(y)
if p == q:
return
if self.rank[p] < self.rank[q]:
self.parent[p] = q
else:
self.parent[q] = p
if self.rank[p] == self.rank[q]:
self.rank[p] += 1
self.count -= 1
如果我們將 0 和 7 進(jìn)行一次合并媒佣。即 union(0, 7) 匕累，則會(huì)發(fā)生如下過(guò)程。
3. 不帶權(quán)并查集
完整代碼如下：
class UnionFind:
def __init__(self, n):
"""
并查集
:param n: 節(jié)點(diǎn)個(gè)數(shù)
"""
# 記錄父節(jié)點(diǎn)
self.parent = {}
# 記錄以該結(jié)點(diǎn)為根結(jié)點(diǎn)的樹的深度
self.rank = {}
# 記錄連通分量的個(gè)數(shù)
self.count = 0
# 初始化
for i in range(n):
self.parent[i] = I
self.rank[i] = 1
self.count += 1
def find(self, x):
"""
查找節(jié)點(diǎn)的父(根)節(jié)點(diǎn)
"""
if x != self.parent[x]:
# 進(jìn)行了路徑壓縮
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
合并兩個(gè)節(jié)點(diǎn)默伍，小的樹掛到大的樹上欢嘿，使樹盡量平衡
"""
p, q = self.find(x), self.find(y)
if p == q:
return
if self.rank[p] < self.rank[q]:
self.parent[p] = q
else:
self.parent[q] = p
if self.rank[p] == self.rank[q]:
self.rank[p] += 1
self.count -= 1
4. 帶權(quán)并查集
實(shí)際上并查集就是圖結(jié)構(gòu)，我們使用了哈希表來(lái)模擬這種圖的關(guān)系也糊。 而上面講到的其實(shí)都是有向無(wú)權(quán)圖炼蹦，因此僅僅使用 parent 表示節(jié)點(diǎn)關(guān)系就可以了。而如果使用的是有向帶權(quán)圖呢狸剃？實(shí)際上除了維護(hù) parent 這樣的節(jié)點(diǎn)指向關(guān)系掐隐，我們還需要維護(hù)節(jié)點(diǎn)的權(quán)重，一個(gè)簡(jiǎn)單的想法是使用另外一個(gè)哈希表 weight 存儲(chǔ)節(jié)點(diǎn)的權(quán)重關(guān)系钞馁。比如 weight[a] = 1 表示 a 到其父節(jié)點(diǎn)的權(quán)重是 1虑省。
如果是帶權(quán)的并查集，其查詢過(guò)程的路徑壓縮以及合并過(guò)程會(huì)略有不同僧凰，因?yàn)槲覀儾粌H關(guān)心節(jié)點(diǎn)指向的變更探颈，也關(guān)心權(quán)重如何更新。比如：
a b
^ ^
| |
| |
x y
如上表示的是 x 的父節(jié)點(diǎn)是 a训措，y 的父節(jié)點(diǎn)是 b伪节，現(xiàn)在我需要將 x 和 y 進(jìn)行合并。
a b
^ ^
| |
| |
x -> y
假設(shè) x 到 a 的權(quán)重是 w(xa)绩鸣，y 到 b 的權(quán)重為 w(yb)怀大，x 到 y 的權(quán)重是 w(xy)。合并之后會(huì)變成如圖的樣子：
a -> b
^ ^
| |
| |
x y
那么 a 到 b 的權(quán)重應(yīng)該被更新為什么呢呀闻？我們知道 w(xa) + w(ab) = w(xy) + w(yb)化借，也就是說(shuō) a 到 b 的權(quán)重 w(ab) = w(xy) + w(yb) - w(xa)。
當(dāng)然上面關(guān)系式是加法总珠，減法屏鳍，取模還是乘法勘纯，除法等完全由題目決定，我這里只是舉了一個(gè)例子钓瞭。不管怎么樣驳遵，這種運(yùn)算一定需要滿足可傳導(dǎo)性。
完整代碼如下：
class WeightedUnionFind:
def __init__(self, n):
"""
:param n: 節(jié)點(diǎn)個(gè)數(shù)
"""
# 記錄父節(jié)點(diǎn)
self.parent = {}
# 記錄到父節(jié)點(diǎn)的權(quán)重
self.weight = {}
for i in range(n):
self.parent[i] = I
self.weight[i] = 0
def find(self, x):
if x != self.parent[x]:
p, w = self.find(self.parent[x])
self.parent[x] = p
self.weight[x] += w
return self.parent[x], self.weight[x]
def union(self, x, y, w):
p_x, w_x = self.find(x)
p_y, w_y = self.find(y)
if p_x == p_y:
return
self.parent[p_x] = p_y
self.weight[p_x] = w + w_y - w_x
