一、什么是并查集并查集Union-Find也称为不相交集合数据结构Disjoint-Set Data Structure是一种用于处理元素分组和集合合并与查询的高效数据结构。它主要支持两种操作合并Union将两个元素所在的集合合并为一个集合。查找Find查询某个元素属于哪个集合通常返回该集合的“代表元”。并查集在解决连通性、动态连通、图论中的连通分量等问题上有着广泛的应用其近乎常数时间的操作复杂度使其成为算法竞赛和工程实践中的利器。二、核心思想与数据结构并查集的核心思想是使用树形结构来表示集合。每个集合用一棵树来表示树的根节点代表元作为该集合的标识。初始时每个元素自成一个集合即自己是自己的根。数据结构通常使用一个父节点数组parent来实现parent[i]表示元素i的父节点。如果parent[i] i则i是所在集合的根节点代表元。三、基础操作与优化1. 初始化初始化时每个元素都是独立的集合即自己是自己的根。class UnionFind { private int[] parent; public UnionFind(int n) { parent new int[n]; for (int i 0; i n; i) { parent[i] i; // 每个元素自成一派 } } }2. 查找Find查找元素所在集合的根节点代表元。朴素实现是沿着父节点一直向上找。public int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; }路径压缩优化在查找过程中将沿途所有节点的父节点直接指向根节点使树的高度降低极大提升后续查找效率。public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩 } return parent[x]; }3. 合并Union将两个元素所在的集合合并。朴素实现是将一个集合的根节点指向另一个集合的根节点。public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 将 rootX 的根指向 rootY } }按秩合并优化为了保持树的平衡避免退化成链我们记录每个树的“秩”如高度或大小总是将秩较小的树合并到秩较大的树上。class UnionFind { private int[] parent; private int[] rank; // 秩高度 public UnionFind(int n) { parent new int[n]; rank new int[n]; for (int i 0; i n; i) { parent[i] i; rank[i] 1; } } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else { parent[rootY] rootX; rank[rootX]; // 高度相同时合并后高度1 } } } }四、完整 Java 实现带优化public class UnionFind { private int[] parent; private int[] rank; // 按秩合并 public UnionFind(int n) { parent new int[n]; rank new int[n]; for (int i 0; i n; i) { parent[i] i; rank[i] 1; } } // 查找带路径压缩 public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } // 合并带按秩合并 public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else { parent[rootY] rootX; rank[rootX]; } } } // 判断两个元素是否连通 public boolean isConnected(int x, int y) { return find(x) find(y); } }五、典型应用场景1. 判断图中节点是否连通给定一个无向图动态添加边实时判断两个节点是否连通。2. 朋友圈问题LeetCode 547有n个人如果a和b是朋友b和c是朋友则a和c也是朋友。求朋友圈的个数。3. 岛屿数量LeetCode 200可以用并查集替代 DFS/BFS 来统计网格中“1”构成的连通块数量。4. 最小生成树Kruskal 算法Kruskal 算法中并查集用于判断加入一条边后是否会形成环。六、复杂度分析空间复杂度O(n)用于存储 parent 和 rank 数组。时间复杂度均摊仅使用路径压缩或按秩合并O(log n)。同时使用路径压缩和按秩合并O(α(n))其中 α(n) 是反阿克曼函数增长极其缓慢可以近似看作常数时间。七、总结并查集是一种简洁而强大的数据结构其核心在于路径压缩和按秩合并两种优化使得合并与查找操作近乎常数时间。掌握并查集能够高效解决许多与连通性、分组相关的算法问题。建议读者动手实现一遍基础版本再逐步加上优化并通过 LeetCode 相关题目如 547、200、684、721进行巩固练习。