并查集用接近常数的均摊代价回答”两个元素是否同组、合并后还剩几个集合”，是动态连通性问题与 Kruskal 最小生成树的标配。本文拆解它的森林模型、两种关键优化与建模套路。

它解决什么问题

大量问题只关心”分组”而不关心”路径”：两个用户是否在同一个社交圈、加入一条边之后图里还剩几个连通块、无向图里这条边会不会构成环。每次用 BFS/DFS 现场搜索要 O(V+E)，而真实场景里关系不断合并、查询海量，搜索派的成本很快失控。并查集换一种思路：把连通关系预先维护在结构里，查询时只需比对两个元素的”集体身份”。

核心原理

把每个集合组织成一棵树，树根充当整个集合的代表元。parent[x] 记录 x 的父节点，根的父节点是它自己；初始时 n 个元素各自成树，即 n 个集合。find(x) 沿父指针一路爬到根，根就是 x 所在集合的身份；union(a, b) 先各自 find 找根，根相同说明已连通，否则把一棵树挂到另一棵的根下。判断连通等价于 find(a) == find(b)；统计连通分量则维护一个计数器，每次真正合并成功才减一。

理解演进路径有助于记住设计动机：Quick Find 让数组直接存集合编号，查询 O(1) 但合并要扫全表；Quick Union 改存父指针，合并只动一个根，却可能养出高树。实用并查集就是在 Quick Union 上叠加两种抑高手段的产物。

深入机制

朴素实现的退化与两种优化

朴素的 Quick Union 任意挂接，极端情况下树退化成一条长链，find 劣化到 O(n)。两种优化从不同方向封堵退化：

  • 按秩（或按大小）合并：永远把小树挂到大树下。直觉是树高只在”规模翻倍”时才可能加一，因此深度上界被压到 O(log n)。
  • 路径压缩：find 返回途中，顺手把路径上的节点直接挂到根下。这次查询多走的每一步，都在为之后的查询铺路。
class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int count;                       // 当前连通分量数

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;                   // 初始各自为根
            size[i] = 1;
        }
    }

    int find(int x) {                        // 两趟路径压缩
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;                // 沿途节点直接挂到根
            x = next;
        }
        return root;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;          // 已连通，合并失败
        if (size[ra] < size[rb]) {
            int t = ra; ra = rb; rb = t;     // 保证 ra 是大树
        }
        parent[rb] = ra;                     // 小树并入大树
        size[ra] += size[rb];
        count--;
        return true;
    }

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

近 O(1) 的直觉

两种优化叠加后，m 次操作的均摊成本是 O(m·α(n))，α 为反阿克曼函数。阿克曼函数增长快到超越常规直觉，其反函数则慢到几乎停滞：n 取到可观测宇宙的原子总数，α(n) 也不超过 4。所以工程与面试中都说”近似常数”，但要注意理论上它不是严格 O(1)，精确表述是均摊 O(α(n))。空间为 O(n)，即 parent 与 size 两个数组。

连通性问题的建模套路

  1. 编号：把对象映射到 0..n-1，二维网格用 i * cols + j 拍平；
  2. 合并：凡是”二者属于同一组”的条件，一律 union；
  3. 回答：connected 答连通性，count 答分量数，union 返回 false 正好暴露冗余边与环。

工程实践

  • 岛屿数量：每块陆地与相邻陆地 union，结束后分量数即岛屿数；陆地动态增加的场景下，并查集比反复重搜自然得多。
  • 冗余连接：依次读入边，第一条两端已然连通的边就是答案——它正是成环的那条。
  • 等式与账户合并：先把所有”相等、同属”关系 union 完，再逐条检查”不等”约束两端是否被误并，冲突即无解；邮箱账户合并也是同一套先并后查的剧本。
  • Kruskal 最小生成树：边按权升序排序，逐条 union，成功则选入，凑满 V-1 条即得 MST。成环判定被压到近 O(1)，总复杂度由排序主导，O(E log E)。
int kruskal(int n, int[][] edges) {          // edges 元素为 {u, v, w}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    int total = 0, picked = 0;
    for (int[] e : edges) {
        if (uf.union(e[0], e[1])) {
            total += e[2];
            if (++picked == n - 1) break;
        }
    }
    return picked == n - 1 ? total : -1;     // -1：图本身不连通
}

也要认清边界：路径压缩会抹掉”当初靠哪条边连通”的信息，所以并查集不支持删边、给不出两点间的具体路径，也无法表达有向可达。离线删除场景可以把操作序列倒过来，把删除变回添加；要维护”x 与 y 的差值或倍数”这类关系，则需带权并查集。

对比与权衡

方案 单次连通查询 动态加边 支持删边 给出路径 适用场景
并查集（双优化） 均摊近 O(1) 均摊近 O(1) 否 否 动态连通性、分量统计
BFS / DFS O(V+E) 需重搜 需重搜 是 静态图、需要路径
Quick Find O(1) O(n) 否 否 查询极多且几乎无合并

面试视角

union 为什么必须挂根而不是直接挂元素？ 集合身份由根代表，只有根对根挂接才能保证两棵树的全体成员身份统一；随手挂中间节点会让部分成员”脱离集体”，连通性判断直接出错。

路径压缩会不会破坏正确性？ 不会。压缩只改变节点在树里的挂载位置，不改变它所属的根，连通信息无损，纯粹是为后续查询提速的结构调整。

能说并查集操作是 O(1) 吗？ 严格说不能。双优化下均摊 O(α(n))，α 增长极慢、实用中恒为常数级，所以工程上称近似 O(1)；面试答出反阿克曼函数才算完整。

并查集能判有向图的环吗？ 不能，它只表达无向连通性，”a 与 b 连通”不蕴含”a 可达 b”。有向判环要用拓扑排序或三色标记 DFS。

二维网格题怎么套并查集？ 把 (i, j) 映射成一维编号 i * cols + j，四方向相邻的陆地做 union；行或列可能很大时改用 Map 存 parent，只为真实出现的格点建节点。

小结

  • 模型一句话：森林加代表元，find 找根、union 挂根、connected 比根。
  • 按秩合并压制树高，路径压缩摊薄查询，双优化把均摊成本压到近 O(1)。
  • 建模三步走：编号、见关系就 union、用 count / connected / union 返回值回答业务问题。
  • 岛屿、冗余连接、Kruskal 是三大经典战场；删边、求路径与有向可达则超出它的能力圈。