考察并查集的两个优化、均摊复杂度和图论中的典型应用。
基本操作
find(x) 找根;union(x,y) 合并两个集合。朴素实现可能退化成链,单次 O(n)。两个优化
find 时把路径上的节点直接挂到根,后续查询接近 O(1)。判断连通分量
components 计数(每成功合并一次减一)。判断环(无向图)
(u,v):如果 find(u) == find(v),说明 u、v 已连通,再加这条边就成环;否则 union。代码骨架
parent = list(range(n))
rank = [0] * n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb: return False
if rank[ra] < rank[rb]: ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]: rank[ra] += 1
return True
应用
坑
题目与答案就在本页;收藏、批注和错题重练在应用内