【算法提高班】并查集
2020-02-20 本文已影响0人
fe_lucifer
关于并查集的题目不少，官方给的数据是 30 道（截止 2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。这类题目如果掌握模板，那么刷这种题会非常快，并且犯错的概率会大大降低，这就是模板的好处。
我这里总结了几道并查集的题目：
大家可以学了模板之后去套用一下上面的三道题，做不出来的可以看看我的题解。
并查集概述
并查集算法，主要是解决图论中「动态连通性」问题的
Union-Find 算法解决的是图的动态连通性问题，这个算法本身不难，能不能应用出来主要是看你抽象问题的能力，是否能够把原始问题抽象成一个有关图论的问题。
如果你对这个算法不是很明白，推荐看一下这篇文章Union-Find 算法详解，讲的非常详细。
你可以把并查集的元素看成部门的人，几个人可以组成一个部门个数。
并查集核心的三个方法分别是union, find, connected。
-
union: 将两个人所在的两个部门合并成一个部门（如果两个人是相同部门，实际山不需要合并）
（图来自 labuladong）
-
find: 查找某个人的部门 leader -
connnected: 判断两个人是否是一个部门的
（图来自 labuladong）
模板
这是一个我经常使用的模板，我会根据具体题目做细小的变化，但是大体是不变的。
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)
如果你想要更好的性能，这个模板更适合你，相应地代码稍微有一点复杂。
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)
大家可以根据情况使用不同的模板。
