關(guān)于并查集的題目不少慈鸠，官方給的數(shù)據(jù)是 30 道（截止 2020-02-20）御雕，但是有一些題目雖然官方?jīng)]有貼并查集標(biāo)簽蛔屹，但是使用并查集來說確非常簡單削樊。這類題目如果掌握模板，那么刷這種題會非惩枚荆快漫贞，并且犯錯的概率會大大降低，這就是模板的好處育叁。
我這里總結(jié)了幾道并查集的題目：
并查集概述
并查集算法迅脐，主要是解決圖論中「動態(tài)連通性」問題的
Union-Find 算法解決的是圖的動態(tài)連通性問題，這個算法本身不難豪嗽，能不能應(yīng)用出來主要是看你抽象問題的能力谴蔑，是否能夠把原始問題抽象成一個有關(guān)圖論的問題。
如果你對這個算法不是很明白龟梦，推薦看一下這篇文章Union-Find 算法詳解树碱，講的非常詳細(xì)。
你可以把并查集的元素看成部門的人变秦，幾個人可以組成一個部門個數(shù)成榜。
并查集核心的三個方法分別是union, find, connected。
-
union: 將兩個人所在的兩個部門合并成一個部門（如果兩個人是相同部門蹦玫，實(shí)際山不需要合并）
（圖來自 labuladong）
-
find: 查找某個人的部門 leader -
connnected: 判斷兩個人是否是一個部門的
（圖來自 labuladong）
模板
這是一個我經(jīng)常使用的模板赎婚，我會根據(jù)具體題目做細(xì)小的變化，但是大體是不變的樱溉。
class UF:
parent = {}
cnt = 0
def __init__(self, M):
n = len(M)
for i in range(n):
self.parent[i] = i
self.cnt += 1
def find(self, x):
while x != self.parent[x]:
x = self.parent[x]
return x
def union(self, p, q):
if self.connected(p, q): return
self.parent[self.find(p)] = self.find(q)
self.cnt -= 1
def connected(self, p, q):
return self.find(p) == self.find(q)
如果你想要更好的性能挣输，這個模板更適合你，相應(yīng)地代碼稍微有一點(diǎn)復(fù)雜福贞。
```python
class UF:
parent = {}
size = {}
cnt = 0
def __init__(self, M):
n = len(M)
for i in range(n):
self.parent[i] = i
self.size[i] = 1
self.cnt += 1
def find(self, x):
while x != self.parent[x]:
x = self.parent[x]
# 路徑壓縮
self.parent[x] = self.parent[self.parent[x]];
return x
def union(self, p, q):
if self.connected(p, q): return
# 小的樹掛到大的樹上撩嚼， 使樹盡量平衡
leader_p = self.find(p)
leader_q = self.find(q)
if self.size[leader_p] < self.size[leader_q]:
self.parent[leader_p] = leader_q
else:
self.parent[leader_q] = leader_p
self.cnt -= 1
def connected(self, p, q):
return self.find(p) == self.find(q)
大家可以根據(jù)情況使用不同的模板。
