【数据结构与算法】Java 实现并查集（Union-Find）

适用读者：初学算法与数据结构的 Java 开发者，或需要在工程中解决“动态连通性”问题的同学。
阅读收获：

1. 搞懂并查集背后的思想与两大经典优化；
2. 掌握一份可直接粘贴到项目里的 Java 代码；
3. 了解实际业务／竞赛里常见的应用场景与使用示例。

1 并查集是什么？

并查集（Disjoint-Set Union，简称 DSU 或 Union-Find）是一种 支持“分组”与“合并”操作 的树状数据结构，核心满足两件事：

* α(n) 是反阿克曼函数，在实际规模内几乎可以视作 O(1)。

为什么并查集能这么快？

• 路径压缩：find 时把搜索路径上的节点直接挂到根节点，下一次查找就更短。
• 按秩 / 按大小合并：union 时总是把“矮”的树或元素更少的集合挂到“高”的树下，最大深度保持对数级别。

2 它能解决哪些场景？

3 数据结构设计

parent[]  // 下标即元素，值为父节点索引，根节点 parent[x] = x
size[]    // 可选：记录每棵树的节点数量（也可用 rank[] 记录高度）

• 初始化：parent[i] = i; size[i] = 1，每个元素自成单元素集合。
• find：递归或迭代向上走，结合路径压缩。
• union：先 find 两个根，如果不同，就按 size / rank 规则合并，同时更新 size。

4 Java 代码实现与详解

代码采用 路径压缩 + 按大小合并，兼顾可读性与性能。

/**
 * 并查集（DSU / Union-Find）
 * Author: WSKH0929
 */
public class UnionFind {
    private final int[] parent;
    private final int[] size;   // 记录根节点的集合大小

    /** 构造函数：n 个元素编号 0 … n-1 */
    public UnionFind(int n) {
        parent = new int[n];
        size   = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 每个节点的父亲先指向自己
            size[i]   = 1;  // 单元素集合大小为 1
        }
    }

    /** 查找根节点（带路径压缩）*/
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归压缩路径
        }
        return parent[x];
    }

    /** 合并两个元素所在的集合，返回是否真的合并成功 */
    public boolean union(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return false;       // 已属于同一集合，无需合并

        // 小树挂到大树，保持近乎平衡
        if (size[rx] < size[ry]) {
            int tmp = rx; rx = ry; ry = tmp;
        }
        parent[ry] = rx;
        size[rx]  += size[ry];
        return true;
    }

    /** 判断两个元素是否在同一集合 */
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    /** 返回集合大小（仅根节点调用准确）*/
    public int size(int x) {
        int rx = find(x);
        return size[rx];
    }
}

关键代码逐行解释

1. 构造函数：一次性分配两条数组，O(n) 内存可控，避免使用 Map 带来的额外装箱与哈希开销。
2. find：递归写法简洁，JVM 对于小深度递归性能友好；若担心栈溢出可改为循环。
3. union：先比较 size，把小集合挂到大集合根上；两条语句同时更新父指针与大小，保持一致性。
4. 连接查询：连通性判断只需两次 find。
5. 复杂度：所有操作均为近似 O(1)，在百万级数据下依旧稳定。

5 复杂度与边界情况

Tips

• 若元素编号不连续，可先用 HashMap<Obj, Integer> 做映射再使用 DSU。
• 在并发环境中需加锁或使用并行 DSU（更高级话题，本文不展开）。

6 示例：动态判断图连通性

假设有 n 台服务器（0 ~ n-1），不断有连线操作 (a, b)，我们想实时判断所有机器是否最终被连成一个网络：

int n = 6;
UnionFind dsu = new UnionFind(n);
int[][] edges = {{0,1},{2,3},{1,2},{4,5},{3,4}};
for (int[] e : edges) {
    dsu.union(e[0], e[1]);
    if (dsu.size(0) == n) {          // 任意取 0 的集合大小 == n → 全网连通
        System.out.println("Now fully connected!");
        break;
    }
}

输出（第 4 次合并后）：

Now fully connected!

7 常见陷阱

1. 误用递归导致栈溢出

   • 对于 n ≈ 10^7 的极端数据，建议改成迭代 + 手动栈或尾递归优化。

2. 并发访问

   • 多线程下读写冲突会破坏树结构，可使用 线程局部并查集 或 锁分段 策略。

3. 忘记路径压缩／按秩合并

   • 两者缺一不可；只打开其中一个时性能可能退化到 O(n)。

4. 误用 size[idx]

   • 只有在 根节点 上读取 size 才准确，其他节点的 size 没有意义。