關于并查集的題目不少傻粘,官方給的數(shù)據(jù)是 30 道(截止 2020-02-20)每窖,但是有一些題目雖然官方?jīng)]有貼并查集
標簽,但是使用并查集來說確非常簡單抹腿。這類題目如果掌握模板岛请,那么刷這種題會非承袷伲快警绩,并且犯錯的概率會大大降低,這就是模板的好處盅称。
我這里總結(jié)了幾道并查集的題目:
大家可以學了模板之后去套用一下上面的三道題肩祥,做不出來的可以看看我的題解。
并查集概述
并查集算法缩膝,主要是解決圖論中「動態(tài)連通性」問題的
Union-Find 算法解決的是圖的動態(tài)連通性問題混狠,這個算法本身不難,能不能應用出來主要是看你抽象問題的能力疾层,是否能夠把原始問題抽象成一個有關圖論的問題将饺。
如果你對這個算法不是很明白,推薦看一下這篇文章Union-Find 算法詳解痛黎,講的非常詳細予弧。
你可以把并查集的元素看成部門的人,幾個人可以組成一個部門個數(shù)湖饱。
并查集核心的三個方法分別是union
, find
, connected
掖蛤。
-
union
: 將兩個人所在的兩個部門合并成一個部門(如果兩個人是相同部門,實際山不需要合并)
(圖來自 labuladong)
-
find
: 查找某個人的部門 leader -
connnected
: 判斷兩個人是否是一個部門的
(圖來自 labuladong)
模板
這是一個我經(jīng)常使用的模板井厌,我會根據(jù)具體題目做細小的變化蚓庭,但是大體是不變的。
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)
如果你想要更好的性能仅仆,這個模板更適合你器赞,相應地代碼稍微有一點復雜。
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ù)情況使用不同的模板港柜。