并查集
并查集一般用于：
将两个集合合并
询问两个元素是否在一个集合当中
基本原理：
每个集合用一棵树来表示。
树根的编号就是整个集合的编号。
每个节点存储他的父节点，使用pre[x]表示x的父节点
问题：
如何判断树根？答 if pre[x] == x
如何求x的集合编号？答 while pre[x] != x: x = pre[x]
如何合并两个集合？答 如何需要合并的两个集合为a、b，那么将b插入到a中即可（或将a插入b中）即pre[b]=a
优化：
路径压缩（常用）：从某个节点a找到其所在集合的根节点r，那么可以将a到根节点路径上各点x直接指向根节点，即使得pre[x] = r
按秩合并（不常用）：对于每个集合有一个rank值，在合并两个集合的时候将rank值较小的插入到rank值较大的中
模版题：合并集合
N = 100010
p = [0] * N
# 查找根节点，并进行路径优化
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
if __name__ == '__main__':
n, m = [int(c) for c in input().split()]
for i in range(1, n + 1):
p[i] = i
for _ in range(m):
op, a, b = [c for c in input().split()]
a, b = int(a), int(b)
if op == "M":
# 将a插入到b中
p[find(a)] = find(b)
else:
if find(a) == find(b):
print("Yes")
else:
print("No")
"""
IN：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
OUT：
Yes
No
Yes
"""维护元素个数：连通块中点的数量
注意：连通块中的点指的是两点之间是连通的，比如从点a可以访问到点b，从点b可以访问到点a，那么a、b两点之间就是连通的，是连通块中的点。
N = 100010
p = [0] * N
cnt = [1] * N
# 查找根节点，并进行路径优化
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
if __name__ == '__main__':
n, m = [int(c) for c in input().split()]
for i in range(1, n + 1):
p[i] = i
for _ in range(m):
recv = input().split(" ")
op = recv[0]
if op == "C":
a, b = int(recv[1]), int(recv[2])
a = find(a)
b = find(b)
if a != b:
# 将a插入到节点b中
p[a] = b
# 维护根节点连通块中的数量
cnt[b] += a
elif op == "Q1":
a, b = int(recv[1]), int(recv[2])
if find(a) == find(b):
print("Yes")
else:
print("No")
else:
a = int(recv[1])
print(cnt[find(a)])
"""
IN:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
OUT:
Yes
2
3
"""Python并查集模版
普通版
class DSU(object):
def __init__(self, n):
# n代表点的个数
self.pre = [0] * n
for i in range(n):
self.pre[i] = i
# 查找x的根节点
def find(self, x: int):
while self.pre[x] != x:
x = self.pre[x]
return x
# 合并两个集合
# False: 说明已经在一个集合中，无需合并
# True: 合并成功
def union(self, a: int, b: int) -> bool:
ar = self.find(a)
br = self.find(b)
if ar == br:
return False
# 将a所在集合插入到b所在集合中
self.pre[ar] = br
return True
if __name__ == '__main__':
# 存在环CASE
# edges = [
# (0, 1), (1, 2), (1, 3),
# (2, 4), (3, 4), (2, 5)
# ]
# 不存在环CASE
edges = [
(0, 1), (1, 2), (1, 3),
(3, 4), (2, 5)
]
n = 6
dsu = DSU(n)
for a, b in edges:
if not dsu.union(a, b):
raise print("存在环")
print("不存在环")按秩合并
class DSU(object):
def __init__(self, n):
# n代表点的个数
self.pre = [0] * n
for i in range(n):
self.pre[i] = i
# rank表示每个集合的高度
self.rank = [0] * n
# 查找x的根节点
def find(self, x: int):
while self.pre[x] != x:
x = self.pre[x]
return x
# 合并两个集合
# False: 说明已经在一个集合中，无需合并
# True: 合并成功
def union(self, a: int, b: int) -> bool:
ar = self.find(a)
br = self.find(b)
if ar == br:
return False
if self.rank[ar] > self.rank[br]:
self.pre[br] = ar
elif self.rank[ar] < self.rank[br]:
self.pre[ar] = br
else:
self.pre[ar] = br
self.rank[br] += 1
return True
if __name__ == '__main__':
# 存在环CASE
# edges = [
# (0, 1), (1, 2), (1, 3),
# (2, 4), (3, 4), (2, 5)
# ]
# 不存在环CASE
edges = [
(0, 1), (1, 2), (1, 3),
(3, 4), (2, 5)
]
n = 6
dsu = DSU(n)
for a, b in edges:
if not dsu.union(a, b):
raise print("存在环")
print("不存在环")路径压缩
class DSU(object):
def __init__(self, n):
# n代表点的个数
self.pre = [0] * n
for i in range(n):
self.pre[i] = i
# 查找x的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
# 如 self.pre = [-1] * n，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
def find(self, x: int):
if self.pre[x] != x:
self.pre[x] = self.find(self.pre[x])
return self.pre[x]
# 合并两个集合
# False: 说明已经在一个集合中，无需合并
# True: 合并成功
def union(self, a: int, b: int) -> bool:
ar = self.find(a)
br = self.find(b)
if ar == br:
return False
# 将a所在集合插入到b所在集合中
self.pre[ar] = br
return True
if __name__ == '__main__':
# 存在环CASE
# edges = [
# (0, 1), (1, 2), (1, 3),
# (2, 4), (3, 4), (2, 5)
# ]
# 不存在环CASE
edges = [
(0, 1), (1, 2), (1, 3),
(3, 4), (2, 5)
]
n = 6
dsu = DSU(n)
for a, b in edges:
if not dsu.union(a, b):
raise print("存在环")
print("不存在环")练习
from typing import List
class DSU(object):
def __init__(self, n):
# n代表点的个数
self.pre = [0] * n
for i in range(n):
self.pre[i] = i
# 查找x的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
# 如 self.pre = [-1] * n，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
def find(self, x: int):
if self.pre[x] != x:
self.pre[x] = self.find(self.pre[x])
return self.pre[x]
# 合并两个集合
# False: 说明已经在一个集合中，无需合并
# True: 合并成功
def union(self, a: int, b: int) -> bool:
ar = self.find(a)
br = self.find(b)
if ar == br:
return False
# 将a所在集合插入到b所在集合中
self.pre[ar] = br
return True
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
dsu = DSU(1010)
for a, b in edges:
if not dsu.union(a, b):
if a > b:
return [b, a]
return [a, b]
return []from typing import List
from collections import defaultdict
class DSU(object):
def __init__(self, n):
# n代表点的个数
self.pre = [0] * n
for i in range(n):
self.pre[i] = i
# 查找x的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
# 如 self.pre = [-1] * n，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
def find(self, x: int):
if self.pre[x] != x:
self.pre[x] = self.find(self.pre[x])
return self.pre[x]
# 合并两个集合
# False: 说明已经在一个集合中，无需合并
# True: 合并成功
def union(self, a: int, b: int) -> bool:
ar = self.find(a)
br = self.find(b)
if ar == br:
return False
# 将a所在集合插入到b所在集合中
self.pre[ar] = br
return True
class Solution:
def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
"""
先判断有没有入度为 2 的点：
没有入度为 2 的点：则一定有首尾相接的圈（意思是箭头方向全是一致，全是顺时针或者逆时针），
此时可以按照无向图的情形处理，删除最后出现的多余的边。
有入度为 2 的点 c，两条边先后出现的顺序是 [a,c] 和 [b,c]：在边集中去掉 [b,c]，
判断剩下的边集中是否存在圈： a. 如果存在圈，则删掉 [a,c]。 b. 不存在圈，则删掉 [b,c].
"""
dd = defaultdict(list)
flag = False
# 找到入度为2的点
for a, b in edges:
dd[b].append(a)
if len(dd[b]) == 2:
flag = True
break
# 选择其中一组移除 （list(dd[b])[0], b）
if flag:
dsu = DSU(1010)
for a, c in edges:
if a == dd[b][1] and c == b:
continue
dsu.union(a, c)
if not dsu.union(dd[b][1], b):
return [dd[b][1], b]
else:
return [dd[b][0], b]
dsu = DSU(1010)
for a, c in edges:
if not dsu.union(a, c):
return [a, c]
return list()参考
最后更新于
这有帮助吗？