深入理解并查集（Java并查集数据结构与Union-Find算法详解）

并查集的基本实现思路

我们可以用一个数组 parent[] 来表示每个元素的父节点：

• 初始时，每个元素的父节点是自己（即 parent[i] = i）。
• Find 操作通过不断向上查找父节点，直到找到根节点。
• Union 操作先找到两个元素的根节点，若不同，则将其中一个根指向另一个。

优化技巧：路径压缩 + 按秩合并

为了提升效率，并查集通常采用两种优化：

1. 路径压缩（Path Compression）：在 Find 时，将路径上的所有节点直接连接到根节点，减少后续查找时间。
2. 按秩合并（Union by Rank）：在 Union 时，总是将较小的树合并到较大的树下，避免树过高。

Java实现并查集

下面是一个完整的、带优化的 Java并查集 实现：

public class UnionFind {    private int[] parent;    private int[] rank;  // 用于按秩合并    private int count;     // 当前集合数量    // 构造函数：初始化 n 个独立集合    public UnionFind(int n) {        parent = new int[n];        rank = new int[n];        count = n;        for (int i = 0; i < n; i++) {            parent[i] = i;   // 自己是自己的父节点            rank[i] = 0;    // 初始秩为0        }    }    // 查找 x 的根节点（带路径压缩）    public int find(int x) {        if (parent[x] != x) {            parent[x] = find(parent[x]);  // 路径压缩        }        return parent[x];    }    // 合并 x 和 y 所在的集合（按秩合并）    public void union(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            // 按秩合并            if (rank[rootX] < rank[rootY]) {                parent[rootX] = rootY;            } else if (rank[rootX] > rank[rootY]) {                parent[rootY] = rootX;            } else {                parent[rootY] = rootX;                rank[rootX]++;            }            count--;  // 集合数量减一        }    }    // 判断 x 和 y 是否在同一集合    public boolean connected(int x, int y) {        return find(x) == find(y);    }    // 获取当前集合数量    public int getCount() {        return count;    }}

使用示例

下面是一个简单的使用场景：判断图中是否存在环。

public static boolean hasCycle(int[][] edges, int n) {    UnionFind uf = new UnionFind(n);    for (int[] edge : edges) {        int u = edge[0], v = edge[1];        if (uf.connected(u, v)) {            return true;  // 已在同一集合，说明成环        }        uf.union(u, v);    }    return false;}

总结

通过本教程，你已经掌握了 Java并查集 的基本原理、优化技巧和完整实现。并查集虽然结构简单，但在解决连通性问题时非常高效，时间复杂度接近常数（阿克曼函数的反函数）。

记住关键词：Java并查集、并查集数据结构、Union-Find算法、Java实现并查集——它们是你深入学习图算法的重要基础！

动手试试吧！你可以用它来解决 LeetCode 上的“省份数量”、“冗余连接”等经典题目。