算法刷题系列（三十六）：并查集——维护动态连通分量

算法刷题系列（三十六）：并查集——维护动态连通分量

当边不断加入时，常见问题是判断两个顶点是否已经连通，或统计当前连通分量数。并查集（Disjoint Set Union，DSU）把每个集合表示成一棵树：根节点是集合代表，树中任意节点沿父指针都能到达这个根。

它适合处理“合并集合”和“查询同属关系”，但不擅长删除边、列出集合内所有路径，或回答一般图上的最短路问题。

两个操作与树高优化

• find(x) 返回 x 所属集合的代表。
• union(a,b) 若两者代表不同，就把两个集合合并。

朴素地随意挂接根节点，树可能退化成链。按集合大小合并时，把较小树挂到较大树下；路径压缩则让查找途中访问的节点直接指向根。两种优化结合后，m 次操作的总复杂度为 O(m α(n)) 的摊还量级，其中 α 是增长极慢的反阿克曼函数。

Java 实现

public class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int components;

    public UnionFind(int count) {
        if (count < 0) {
            throw new IllegalArgumentException("count must be non-negative");
        }
        parent = new int[count];
        size = new int[count];
        components = count;
        for (int i = 0; i < count; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int value) {
        check(value);
        if (parent[value] != value) {
            parent[value] = find(parent[value]);
        }
        return parent[value];
    }

    public boolean union(int first, int second) {
        int rootA = find(first);
        int rootB = find(second);
        if (rootA == rootB) {
            return false;
        }
        if (size[rootA] < size[rootB]) {
            int temp = rootA;
            rootA = rootB;
            rootB = temp;
        }
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
        components--;
        return true;
    }

    public boolean connected(int first, int second) {
        return find(first) == find(second);
    }

    public int componentCount() {
        return components;
    }

    private void check(int value) {
        if (value < 0 || value >= parent.length) {
            throw new IndexOutOfBoundsException("value out of range");
        }
    }
}

Python 实现

class UnionFind:
    def __init__(self, count: int) -> None:
        if count < 0:
            raise ValueError("count must be non-negative")
        self.parent = list(range(count))
        self.size = [1] * count
        self.components = count

    def find(self, value: int) -> int:
        if not 0 <= value < len(self.parent):
            raise IndexError("value out of range")
        if self.parent[value] != value:
            self.parent[value] = self.find(self.parent[value])
        return self.parent[value]

    def union(self, first: int, second: int) -> bool:
        root_a = self.find(first)
        root_b = self.find(second)
        if root_a == root_b:
            return False
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def connected(self, first: int, second: int) -> bool:
        return self.find(first) == self.find(second)

dsu = UnionFind(5)
assert dsu.union(0, 1)
assert dsu.union(1, 2)
assert not dsu.union(0, 2)
assert dsu.connected(0, 2)
assert not dsu.connected(0, 4)
assert dsu.components == 3

正确性与不变量

每个节点的父指针最终指向其所在树的唯一根；find 只改变通往根的路径，不改变根的身份，所以不改变集合划分。union 仅在两个根不同时连接它们，恰好合并两个原本不相交的集合，并把分量数减一。若根相同，两个元素早已同属一组，重复合并不应改变计数。

空间为 O(n)；单次操作的最坏时间分析不如摊还界直观，路径压缩加按大小合并后，连续 m 次操作的总成本为 O(m α(n))。

容易遗漏的细节

• 只有根节点的 size 有意义；合并后不能读取旧根的大小来代表整个集合。
• 每次成功合并分量数减一，重复合并不减。
• 节点编号应限制在 [0,n)；否则数组访问会越界。
• 并查集记录的是连通等价关系，不保留具体边或路径。
• 普通 DSU 支持合并、不支持拆分；删除边可能让原连通块分裂，通常需要离线算法或动态连通性数据结构。

遇到持续加边的连通性题，先判断是否只关心集合关系。如果是，并查集往往能把整图遍历转换成近乎常数摊还的查询。