数据结构与算法 / 系统课时

用并查集合并动态连通分量

用并查集合并动态连通分量

当边不断加入、题目反复询问“两点是否连通”或“当前还有多少个集合”时,每次重新 DFS 都会重复工作。并查集把每个连通分量压成一棵代表树,通过查找根节点和合并根节点,高效维护只增不减的连通关系。

学习目标

  • 理解父节点数组如何表示多个互不相交的集合。
  • 能实现路径压缩与按大小合并,并解释两者为什么能降低树高。
  • 能判断并查集适合增量连通、离线合并,而不擅长直接处理删除边。

用代表元维护集合

并查集为每个元素维护一个父节点 parent[x]。根节点满足 parent[x] == x,它就是所在集合的代表元。判断两个元素是否属于同一集合,只需要比较它们最终找到的根是否相同。

合并两个集合时,不能只把任意节点互连,而应先分别找到两个根,再把一棵树的根挂到另一棵树的根上。这样集合结构始终是一片森林。

并查集的合并与路径压缩

如果每次合并都随意挂接,树可能退化成很长的链。常见的两个优化是:find 返回时执行路径压缩,让沿途节点直接指向根;union 时按集合大小或秩合并,让较小的树挂到较大的树上。

实现带路径压缩的并查集

下面的完整 Java 程序维护 6 个节点。边依次加入后,可以查询任意两点是否连通,也可以直接读取当前连通分量数量。

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

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            components = n;

            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                // 递归返回时把路径上的节点直接连到根。
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) {
                return false;
            }

            // 小集合挂到大集合,避免树持续变高。
            if (size[rootA] < size[rootB]) {
                int tmp = rootA;
                rootA = rootB;
                rootB = tmp;
            }

            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            components--;
            return true;
        }

        boolean connected(int a, int b) {
            return find(a) == find(b);
        }

        int components() {
            return components;
        }
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(6);

        uf.union(0, 1);
        uf.union(1, 2);
        uf.union(3, 4);
        uf.union(2, 4);

        System.out.println(uf.connected(0, 4));
        System.out.println(uf.connected(0, 5));
        System.out.println(uf.components());
    }
}

预期输出:

text
true
false
2

四次合并后,0、1、2、3、4 已经属于同一集合,节点 5 仍然独立,因此最终有两个连通分量。

为什么这两个优化有效

路径压缩优化的是后续查找:一旦某条长路径被访问,路径上的节点会直接靠近根。按大小合并优化的是合并当下:尽量避免把大树挂到小树下面。二者一起使用后,单次 find 或 union 的均摊代价接近常数,通常记为 O(α(n)),其中 α 是增长极慢的反阿克曼函数。

维护分量数量时也不必重新遍历所有节点。初始化为 n,只有当两个原本不同的根成功合并时才减一;如果两点本来就在同一集合,union 应返回失败并保持计数不变。

适用边界

并查集最适合“连接只会增加”的问题,例如逐条加入道路后查询城市是否连通、合并账户、判断无向图是否出现冗余边,以及先收集查询再离线处理的连通性问题。

它不直接保存两点之间的具体路径,也不擅长边删除。删除一条边后,一个集合可能裂成多个部分,而并查集没有足够信息恢复这种拆分。需要频繁删除边时,应考虑离线逆序、回滚并查集或其他动态连通数据结构。

判断是否该用并查集,可以抓住一句话:如果题目主要操作是“把两个集合合起来”,主要查询是“是否同组或还有几组”,并且关系总体只增不减,并查集通常比反复图搜索更合适。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用并查集合并动态连通分量

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通