并查集算法应用：连通、合并与判环

我真正开始理解“并查集算法应用：连通、合并与判环”，不是在背完某段代码之后，而是在一次次写错之后。最明显的问题是：并查集代码很短，我却一度只会照着模板写 parent 数组，不清楚它为什么适合动态合并，却不擅长删除和恢复路径。把这些错误重新摊开来看，我才找到比口诀更可靠的理解方式。

并查集在数据结构篇里已经讲过基本结构：父数组、路径压缩、按秩合并。到了算法篇，我们更关心它能解决哪些问题。

并查集最适合回答一句话：两个元素现在是否属于同一个集合？

并查集适合什么问题

并查集应用

图：并查集用代表元判断两个元素是否属于同一个集合

常见应用：

无向图连通分量。
动态合并集合。
判断新增边是否形成环。
Kruskal 最小生成树。
岛屿数量动态变化。
等式约束一致性。
账户合并。

它不擅长：

删除边。
查询两点之间具体路径。
维护有向可达关系。
频繁拆分集合。

基础模板

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) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    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;
        }
        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;
    }
}

union 返回 false 表示两个点原本已经连通，这在判环时很有用。

无向图判环

给定无向图边列表，如果某条边的两个端点已经连通，再加入这条边就会形成环。

boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] e : edges) {
        if (!uf.union(e[0], e[1])) {
            return true;
        }
    }
    return false;
}

注意：这个方法适合无向图。有向图判环通常用 DFS 三色标记或拓扑排序。

账户合并

如果两个账号拥有相同邮箱，就认为属于同一个人。可以把账号编号作为集合元素，把共享邮箱的账号 union 起来。

思路：

遍历每个账号的邮箱。
邮箱第一次出现时记录所属账号。
邮箱再次出现时，把两个账号合并。
最后按代表元收集邮箱。

这类问题体现了并查集的工程价值：它把“多条关系连接成多个群组”变得很自然。

岛屿数量

二维网格里，每个陆地格子可以看成一个节点，相邻陆地 union 到一起。最后集合数量就是岛屿数量。

动态岛屿问题中，格子会逐步从水变成陆地。每加入一个陆地，岛屿数先加一，再和周围陆地合并，成功合并一次岛屿数减一。

等式约束

例如：

a == b
b == c
a != c

先把所有等式合并，再检查不等式两端是否已经连通。如果连通，就矛盾。

这个模式常见于约束一致性判断。

并查集复杂度

路径压缩 + 按大小合并后，单次操作的均摊复杂度接近常数，通常写作 O(α(n))。α(n) 是反阿克曼函数，在现实数据规模下可以近似看成小于 5。

但不要因此把并查集当万能结构。它快，是因为它只回答集合代表元，不回答集合内部路径细节。

常见错误

只压缩路径，不按大小合并，极端情况下树仍可能变高。
忘记 count--。
把有向图判环错误套用并查集。
需要路径信息的问题误用并查集。
二维坐标映射成一维编号时下标写错。

面试题

并查集适合解决什么问题？
路径压缩有什么作用？
为什么无向图判环可以用并查集？
有向图判环为什么不能直接套并查集？
动态岛屿数量如何维护？

小结

并查集是一种非常克制但强大的结构。它不关心路径，只关心集合。只要问题能转化成“合并关系”和“判断是否同组”，它就非常合适；如果问题要查询方向、路径、删除或拆分，就要换别的工具。