關(guān)于并查集的題目不少羡藐，官方給的數(shù)據(jù)是 30 道（截止 2020-02-20），但是有一些題目雖然官方?jīng)]有貼并查集標(biāo)簽悯许，但是使用并查集來說確非常簡單仆嗦。這類題目如果掌握模板，那么刷這種題會(huì)非诚群荆快瘩扼，并且犯錯(cuò)的概率會(huì)大大降低，這就是模板的好處垃僚。
我這里總結(jié)了幾道并查集的題目：
大家可以學(xué)了模板之后去套用一下上面的三道題集绰，做不出來的可以看看我的題解。
并查集概述
并查集算法谆棺，主要是解決圖論中「動(dòng)態(tài)連通性」問題的
Union-Find 算法解決的是圖的動(dòng)態(tài)連通性問題栽燕，這個(gè)算法本身不難，能不能應(yīng)用出來主要是看你抽象問題的能力改淑，是否能夠把原始問題抽象成一個(gè)有關(guān)圖論的問題纫谅。
如果你對(duì)這個(gè)算法不是很明白，推薦看一下這篇文章Union-Find 算法詳解溅固，講的非常詳細(xì)。
你可以把并查集的元素看成部門的人兰珍，幾個(gè)人可以組成一個(gè)部門個(gè)數(shù)侍郭。
并查集核心的三個(gè)方法分別是union, find, connected。
-
union: 將兩個(gè)人所在的兩個(gè)部門合并成一個(gè)部門（如果兩個(gè)人是相同部門掠河，實(shí)際山不需要合并）
（圖來自 labuladong）
-
find: 查找某個(gè)人的部門 leader -
connnected: 判斷兩個(gè)人是否是一個(gè)部門的
（圖來自 labuladong）
模板
這是一個(gè)我經(jīng)常使用的模板亮元，我會(huì)根據(jù)具體題目做細(xì)小的變化，但是大體是不變的唠摹。
class UF:
parent = {}
cnt = 0
def __init__(self, M):
# 初始化 parent 和 cnt
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)
如果你想要更好的性能爆捞，這個(gè)模板更適合你，相應(yīng)地代碼稍微有一點(diǎn)復(fù)雜勾拉。
class UF:
parent = {}
size = {}
cnt = 0
def __init__(self, M):
# 初始化 parent煮甥，size 和 cnt
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ù)情況使用不同的模板。
