15.3 并查集

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

营地之间的路不断增加

地图上最初有若干互不相连的营地。每修好一条路，两个连通区域就合成一个。向导反复询问：“A 和 B 现在能互相到达吗？整张地图还剩多少个连通分量？”

若道路只增加、不删除，并查集（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):
        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):
        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("并查集检查通过")

原页调用了 connected()，实现中却没有这个方法；这里把公开合同补齐，并统一检查非法编号。重复合并返回 False，不会再次减少分量数。

为什么树不会越接越高

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

find 还执行路径减半：向根移动时，让当前节点直接指向祖父。以后再查询同一路径，经过的节点会更少。

按大小（或按秩）合并与路径压缩同时使用时，包含 m 次操作的序列总时间是 O(m α(n))，其中 α 是反 Ackermann 函数。这个结论是摊还界，不表示每一次 find 都独立拥有相同的最坏上界。工程上它增长极慢，但专业表述仍应写 α(n)，而不是用“宇宙里永远小于某常数”代替定义。

Kruskal 修路时只问会不会成环

向导按造价从低到高审查道路。若两端营地已经属于同一连通区域，再铺这条路只会形成环；否则就把两个区域合并。并查集恰好回答这一问，却不会替 Kruskal 排序道路。

Kruskal 最小生成树按边权从小到大检查边 (u, v)：

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

并查集在这里负责快速回答“是否形成环”。边的排序仍占 O(E log E)，并查集不会把整个 Kruskal 算法变成 O(E α(V))。

另一个常见用途是离线动态连通性。若事件包含删除，可以倒序处理：正向的删除在倒序中变成加入。但这种技巧需要问题允许离线读取全部事件，也不能处理所有类型的查询。

路牌系统不能自己绕成圈

压缩路径会频繁改写 parent，按大小合并又只在根上维护统计。想确认地图没有被改坏，就要把几条不变量写出来，而不是只试两个营地。

任何时刻都应满足：

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

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

动手验证合并序列

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

连通分量合拢之后

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