15.3 并查集

前置：树与摊还分析。并查集支持合并集合与判断连通，不保存两点之间的具体路径。

节点之间的路不断增加

若道路只增加、不删除，并查集（disjoint-set union，DSU）很适合这份合同。每个集合选择一个代表元。find(x) 找到代表元，union(a, b) 把两个代表元所在的树接起来；两个元素代表元相同，就属于同一集合。

它不会告诉你具体经过哪些边。需要还原路径、处理最短路或频繁删除边时，应选择别的结构或离线算法。

让父指针更快抵达根

class UnionFind:
    def __init__(self, size):
        if not isinstance(size, int) or isinstance(size, bool) or size < 0:
            raise ValueError("size must be a non-negative integer")
        self._parent = list(range(size))
        self._tree_size = [1] * size
        self.component_count = size

    def _check(self, element):
        if (
            not isinstance(element, int)
            or isinstance(element, bool)
            or not 0 <= element < len(self._parent)
        ):
            raise IndexError(f"element out of range: {element!r}")

    def find(self, element):
        self._check(element)
        while element != self._parent[element]:
            self._parent[element] = self._parent[self._parent[element]]
            element = self._parent[element]
        return element

    def union(self, left, right):
        self._check(left)
        self._check(right)
        left_root = self.find(left)
        right_root = self.find(right)
        if left_root == right_root:
            return False

        if self._tree_size[left_root] < self._tree_size[right_root]:
            left_root, right_root = right_root, left_root
        self._parent[right_root] = left_root
        self._tree_size[left_root] += self._tree_size[right_root]
        self.component_count -= 1
        return True

    def connected(self, left, right):
        self._check(left)
        self._check(right)
        return self.find(left) == self.find(right)

    def component_size(self, element):
        return self._tree_size[self.find(element)]

if __name__ == "__main__":
    groups = UnionFind(10)
    assert groups.union(0, 1)
    assert groups.union(1, 2)
    assert not groups.union(0, 2)
    assert groups.union(3, 4)
    assert groups.connected(0, 2)
    assert not groups.connected(0, 3)
    assert groups.union(2, 3)
    assert groups.connected(0, 4)
    assert groups.component_size(4) == 5
    assert groups.component_count == 6
    print("并查集检查通过")

元素编号固定为 0..size-1，不能动态增加；空并查集的分量数为 0，但没有合法元素可查询。构造器拒绝负数、非整数和布尔值，方法对非法编号抛 IndexError。两个参数均通过检查后才执行查找，避免右参数错误时先修改左路径。重复合并返回 False，不会再次减少分量数。find 和 connected 也会修改父指针，不能当作无副作用的并发读取。

为什么树不会越接越高

若随意把一棵根接到另一棵根上，输入顺序可以造出长链。按大小合并规定：小树的根接到大树根下。一个节点因小树接到大树而增加一层深度时，它所属集合的大小至少翻倍，所以仅靠这条规则，树高也不超过 O(log n)。

find 还执行路径减半：向根移动时，让当前节点直接指向祖父。以后再查询同一路径，经过的节点通常会更少。根是集合标识，不保证是最小编号；后续合并也可能改变代表元。

按大小（或按秩）合并与路径压缩同时使用时，n 个元素的初始化为 Θ(n)，之后 m 次操作的总时间上界为 O(m α(n))，合计 O(n+m α(n))，其中 α 是反 Ackermann 函数。这个结论是摊还界，不表示每一次 find 都独立拥有相同的最坏上界。单次查找的最坏界仍可用 O(log(n+1)) 表示，存储为 Θ(n)。Princeton 的路径减半实现也同时列出初始化、单次操作与序列摊还界。α(n) 增长极慢，但不应被一个脱离规模范围的常数替代。

Kruskal 修路时只问会不会成环

对无向带权图，Kruskal 按边权从小到大检查边 (u, v)；连通图得到最小生成树，不连通图得到最小生成森林：

• 若 u 与 v 已连通，加入该边会形成环，跳过；
• 否则加入边，并执行 union(u, v)。

并查集在这里负责快速回答“是否形成环”。边的排序仍占 O(E log(E+1))。连同 V 个顶点的初始化，常见实现总时间为 O(V+E log(E+1)+E α(V))；并查集不负责有向可达性，也不会消除排序成本。

另一个常见用途是离线动态连通性。若事件只有删边与连通性查询，可以先建立最终图，再倒序把删除变成加边。若正向同时存在加边，倒序又会遇到删边，普通并查集仍然不够，通常需要进一步的离线分解和可回滚并查集。这类方法要求能预先读取完整事件序列。

父指针必须构成森林

任何时刻都应满足：

1. 根节点的 parent[root] == root；
2. 每个节点沿父指针最终抵达某个根，不形成环；
3. tree_size 只在根位置有公开意义；
4. 成功合并两个不同根时，分量数恰好减一。

若 component_count 变得过小，先检查重复合并是否仍减计数。若路径压缩后出现环，检查更新父指针时是否始终朝祖先方向移动。不要在 union 中比较原元素的大小字段；只有根保存集合大小。

动手验证合并序列

1. 用一个朴素的集合标签数组作 oracle，随机对照 connected。
2. 记录没有路径压缩、只有按大小合并时的最大树高。
3. 把路径减半改成两遍完整压缩，比较父数组的变化。
4. 用并查集实现 Kruskal，并同时返回所选边，而不只返回总权重。
5. 解释为什么普通并查集不能直接删除一条已经合并的边。

连通分量合拢之后

并查集舍弃了路径细节，只保留集合代表元，因此合并和连通判断很快。下一篇的线段树保留的是另一类摘要：每个区间的聚合结果，以便在更新后只重算受影响的祖先。