Skip to content
Nahida-aa

Union-Find

graph BT
    2((2)) --"fa[2]"-->  1((1))
    3((3)) --"fa[3]"-->  1
    4((4)) --"fa[4]"-->  3
    5((5)) --"fa[5]"-->  3
    8((8)) -->  7((7))
    7 -->  6((6))

overview

Section titled “overview”

它可以高效地解决以下问题:

  1. 合并 (Union) ：将两个集合合并为一个集合 (合并对应的树)。
  2. 查询 (Find) ：查询某个元素属于哪个集合 (通常通过找到集合的代表元素, 即根节点)。

并查集的核心思想是用一个数组表示集合，通过路径压缩和按秩合并优化，使得查询和合并操作的时间复杂度接近常数 (摊还时间复杂度为 ，其中 是反阿克曼函数，增长极慢)

find

Section titled “find”
所在集合的根节点的值表示是根节点递归调用沿着树向上找

通常在判断是否可达, 连通性问题时 进行查询, 如需要判断 u, v 是否属于同一个集合, 则可以判断 find(u) == find(v)

# 例如 fa[4] = 3 -> fa[3] = 1 -> fa[1] = 1
def find(x):
    if fa[x] == x:
        return x
    return find(fa[x])
# or 如下写法
def find(x):
    return x if fa[x] == x else find(fa[x])


find = lambda x: x if fa[x] == x else find(fa[x])

union

Section titled “union”

有时需要将两个集合合并(例如两个家庭结婚), 例如将 u, v 合并为同一个集合, 则可以将 u 的根节点的父节点设为 v 的根节点

graph BT
    1 --> 6
    2((2)) -->  1((1))
    3((3)) -->  1
    4((4)) -->  3
    5((5)) -->  3
    8((8)) -->  7((7))
    7 -->  6((6))
def union(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        fa[x] = y
# or
def union(x, y):
    if find(x) != find(y): fa[find(x)] = find(y)

[!info]- python 的 = 操作是 引用模型 (Reference Model) a = b{:py} 是将 a 指向 b

# 赋值语法: 变量 = 字面量; 实际上是
b = [1, 2, 3]
# 引用语法: 变量 = 变量
a = b
a[0] = 4
print(b) # [4, 2, 3]

路径压缩

Section titled “路径压缩”
flowchart LR
    subgraph 第一阶段
        2((2)) -->  1((1))
        3((3)) -->  1
        4((4)) -->  3
        5((5)) -->  3
    end


    subgraph 第二阶段
        2.2((2)) -->  2.1((1))
        2.3((3)) -->  2.1
        2.4((4)) -->  2.1
        2.5((5)) -->  2.1
    end


    第一阶段 --路径压缩--> 第二阶段

路径压缩是指在查找过程中, 将访问过的节点的父节点直接指向根节点, 以减少树的高度, 提高查询效率

def find(x):
    if fa[x] == x: # 如果 x 是根节点
        return x
    fa[x] = find(fa[x]) # 路径压缩
    return fa[x]

我们通过对查询操作引入路径压缩, 可以对比 find

模板总结

Section titled “模板总结”
递归模板
fa = list(range(n)) #
def find(x):
    if fa[x] == x: return x
    fa[x] = find(fa[x]) # 路径压缩
    return fa[x]
def union(x, y):
    if find(x) != find(y):
        fa[find(x)] = find(y)

可以不用考虑迭代模板, 一般不会爆栈的

迭代模板
fa = list(range(n)) #
def find(x):
    root = x
    while fa[root] != root:
        root = fa[root]
    while fa[x] != x: # 路径压缩
        fa[x], x = root, fa[x]
    return root
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        fa[root_x] = root_y
t1