并查集动态连通性

并查集、MST 与离线激活 · HTML

数学 / 逻辑形态

对象集 V 上执行 union(a,b)、find(x)、connected(a,b)；关系是等价关系，边只增加。

识别信号

• 反复合并两组并查询同组
• 只关心连通而不关心具体路径
• 关系具有传递性
• 边在线加入而不删除
• 需要组件数或组件大小

容易误判的相似信号

核心不变量

每个集合是一棵父指针树，根是唯一代表元；size 仅在根处有效。

状态、转移与处理顺序

Python 骨架

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1] * n
        self.components = n
    def find(self, x):
        while x != self.p[x]:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b: return False
        if self.sz[a] < self.sz[b]: a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]
        self.components -= 1
        return True
    def connected(self, a, b):
        return self.find(a) == self.find(b)

正确性思路

1. 初始每个元素自成集合，不变量成立。
2. union 只连接不同集合的根，恰好合并两个等价类。
3. 路径压缩只改挂同树祖先，不改变代表元。
4. 归纳得 find 相等当且仅当已处理关系使两点连通。

复杂度

边界条件

• 重复 union 不应修改计数
• a==b 时天然连通
• size 必须从根读取
• 标签稀疏时先坐标压缩
• n=0 的接口语义需约定

错误模式

选择与排除规则

• 只有增边连通查询：首选 DSU。
• 需要实际路径或距离：使用图搜索。
• 删边能倒序变成加边：转离线 DSU。
• 对象标签不连续：先映射到紧凑整数。

相关模板

原创微型例子

Recall prompts

• 为什么比较前必须 find？
• 路径压缩和按规模合并各解决什么？
• 哪类删边能倒序后继续使用 DSU？

我的补充