1. 从判断两个人是不是一个圈子说起我在刚开始接触并查集的时候并没有意识到它到底能解决什么实际问题毕竟当时手里只有一本薄薄的数据结构教材里面把它归为树的应用里不起眼的一小节。直到后来做了几个社交网络相关的项目遇到了一个非常直观的需求系统里有成千上万个用户用户之间有关系数据比如互相关注、同在一个群聊我需要随时回答A用户和B用户是否在同一个圈子/连通分量里而且在运行过程中圈子还在不断合并——今天张三和李四认识了两个圈子就应该变成一个。这种需求用最朴素的想法怎么做给每个圈子分配一个编号用一个数组记录每个人属于哪个圈子合并两个圈子时把其中一整个圈子的人全部重新编号。圈子少还行圈子一多、人数一多每次合并都是O(n)的遍历分分钟被压垮。而且这还只是数据量上万的场景如果飙到百万、千万级这种做法根本没法用。后来我才发现数据结构和算法里早就有一个专门解决这类问题的方案就是并查集Union-Find。它的核心能力概括起来只有三件事判断两个元素是否在同一个集合里把两个集合合并成一个以及在这两个操作都执行得非常快的前提下支持大量动态的合并和查询。为什么说它设计得精巧因为它在最理想的优化之后单次操作的时间复杂度可以接近常数级别几乎可以认为是O(1)量级但代码却短得令人发指二三十行就能写完一个完整的实现。这篇内容适合谁如果你是刚学数据结构、正在为算法题头疼的学生并查集是你绕不开的一个基础武器如果你是在实际工作中要处理连通性、分组、合并这类需求的后端开发它也是一个非常趁手的小工具。这篇文章会从问题本身出发把并查集为什么这样设计、每一步优化的动机是什么、代码怎么写、实际场景怎么用一步步讲清楚。最后当然也少不了我自己在实践中踩过的一些坑。2. 暴力做法为什么会失败要理解并查集的精巧最好的办法是先看看我之前说的那种朴素方案到底卡在哪。我把它展开说因为这决定了后续所有设计的走向。最直接的思路给每一个集合设置一个唯一的编号用一个 leader 数组leader[i] 就表示元素 i 属于哪个集合。查询两个元素是否连通只需要看 leader[a] 是否等于 leader[b]这是O(1)的操作。问题出在合并上。比如集合A现在有1万个元素集合B有5千个元素要把它们合并成一个集合遍历这1万个元素把它们的 leader 值统一改成新的编号合并一次就是O(n)如果合并操作的频率高一些比如M次整体复杂度就是O(M × n)这在大规模数据下根本接受不了。另一种思路是图模型。把元素间的关系看作一条边把所有元素看作节点那么是否在一个连通分量里这个问题就等价于在无向图上判断两个节点是否连通。这时可以用深度优先搜索DFS或广度优先搜索BFS来处理。每查询一次就从头对整个图做一次遍历把当前节点能到达的所有节点记录下来看看目标节点是否在其中。这种方法看上去比数组方案通用一些但实际上更慢因为每次查询都要重新遍历一遍图而且如果边非常多遍历的成本会非常高。还有第三种思路就是维护多个列表每个列表存一个集合的所有元素合并时把一个列表的内容追加到另一个列表后面然后把自己清空。这个方案在合并的时候能省掉一部分遍历只要把其中一个列表的元素搬到另一个列表里就行。但问题是查询的时候呢还是要遍历列表才能判断一个元素在不在里面查询退化成O(n)。这四个字可以总结这些朴素方案的问题重开销。它们把合并和查询的成本都没有降下来而真实场景里往往是查询和合并穿插出现、数量都很大所以我们需要一个数据结构让这两个操作都能做到足够快并且实现还足够简单。这就是并查集存在的意义。3. 并查集的树形结构与找根并查集的思路其实特别朴素就是用一棵树来代表一个集合。这里有一个非常关键的思维转变不关心集合里元素的先后顺序也不关心树长什么样只关心这棵树是谁。整个并查集只需要一个 parent 数组。parent[i] 表示元素 i 的父节点是谁。如果某个节点是它自己的父节点即 parent[i] i那它就是这棵树的根节点。在并查集里根节点就是这棵树的代表也就是集合的标识符。初始状态每个元素都是单独的节点parent[i] i表示每个元素自己构成一个集合自己就是根。这个初始化动作简单却特别容易出错我在后面的章节会专门讲。然后是这个数据结构最重要的两个操作find 和 union。find(x) 做的事情是从节点 x 出发一直顺着 parent 指针往上走直到走到根节点然后返回这个根节点。这个操作可以被理解为查找 x 所在集合的编号。由于整个结构是一棵树最坏情况下从某个叶子节点一路走到根要走一整条链这也是并查集性能的关键所在。union(x, y) 做的事情是把 x 所在的集合和 y 所在的集合合并。合并的方法非常简单先分别 find(x) 和 find(y)拿到两个集合的根节点然后把其中一个根节点的 parent 指向另一个根节点两棵树就变成了一棵树。判断两个元素是否在同一个集合里就更有意思了分别 find(x) 和 find(y)如果两个根节点相同就说明它们在同一棵树上即属于同一个集合。这三个操作凑在一起就是并查集的全部核心了。但你会发现一个隐患如果树长得非常深find 操作每次都要走很长一条链性能还是会退化。比如我们每次都把深度大的树接在深度小的树下面树会变得越来越长最坏情况下会变成一个链表find 就退化成O(n)了。解决这个问题正是并查集的优化精髓所在我把它留到代码实现的章节里详细展开。4. 代码实现的三个版本从能用、好用到高效4.1 朴素版先把逻辑跑通我先从最朴素的版本写起。这个版本只保证功能正确不追求性能。它是最好的教学起点也是理解后面优化的基础。class UnionFind { private int[] parent; // 初始化每个元素自成一棵树 public UnionFind(int n) { parent new int[n]; for (int i 0; i n; i) { parent[i] i; } } // 找到根节点集合的代表 // 最坏情况会沿着链一直走到根 public int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; } // 合并两个集合 public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } parent[rootX] rootY; } // 判断两个元素是否属于同一个集合 public boolean isConnected(int x, int y) { return find(x) find(y); } }这段代码很简单但它有三点值得注意。第一find 的循环条件 parent[x] ! x含义是只要我不是根就继续往上走因为根节点的特征就是 parent[i] i。第二union 里首先要判断两个根是否相同——如果相同说明它们本来就在一个集合强行再挂一次会破坏结构。第三union 的方向会影响树的深度在这个朴素的版本里我没做任何控制所以树的高度是完全不可预测的最坏情况下会退化。这个版本在数据规模小或者操作次数少的时候可以用但一旦数据量大了就会力不从心。我见过有人拿这种朴素版本去跑百万级数据直接卡到超时。别问我怎么知道的。4.2 路径压缩让find不再走冤枉路针对 find 退化成深链的问题并查集有一个非常优雅的优化叫路径压缩Path Compression。它的思想是既然 find 是为了找到根那么在这个过程中经过的所有节点它们的根都是同一个。那我干脆把这整条链上的节点直接都挂到根节点下面去。这样下次再从这些节点出发找根时就会一路平趟一步到位时间复杂度趋近于O(1)。路径压缩的代码写在 find 里写法有两种。一种是用递归实现代码最简洁public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }这里有个非常关键的逻辑先递归地去寻找根节点然后在回溯的时候把当前节点的 parent 直接指向根节点。这样一来原本是一条长链的路径被压缩成一层扁平的结构。另一种是迭代实现避免了递归可能带来的栈溢出风险在数据量极大时更安全public int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; } // 第二次遍历把路径上所有节点直接接到根上 while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }这个迭代版本做的事情和递归版本完全一样只是它先找到根再走一遍把路径上的节点都挂到根上。虽然看起来多了一次循环但它是非递归版本在深度非常夸张的时候更稳健。我个人在实际项目中更倾向于迭代版因为我不希望一次 find 调用在极端情况下把调用栈打爆。4.3 按秩合并控制树的高度路径压缩已经能把 find 降到几乎常数级了但这还不够。因为 tree 的高度在最开始建立的时候是很可能非常不平衡的如果不控制 union 的方向路径压缩只能事后补救最好的方案是在合并时就让树保持矮胖。这就是按秩合并Union by Rank。思路极简用另一个数组 rank[i] 表示以 i 为根的那棵树的高度或者说树的秩合并时永远把矮树接到高树下。如果两棵树高度相同就把一棵接到另一棵下面同时把新根的高度加一。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) { return; } // 矮树接到高树下 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 高度相等一个接一个下面高度1 parent[rootX] rootY; rank[rootY]; } } public boolean isConnected(int x, int y) { return find(x) find(y); } }到了这个版本并查集的单次 find 和 union 操作的时间复杂度就已经非常接近O(1)了准确说是反阿克曼函数级别这个数学概念不用抠太细知道它增长极慢、实际应用可以当常数看就够了。有人可能会问路径压缩已经有了为什么还要按秩合并这是因为两者解决的问题角度不同路径压缩是事发之后把路径变平而按秩合并是从一开始就阻止树变深。两者结合的效果是最好的。我实测过一个百万节点的案例只用路径压缩时偶尔还能看到较深层的递归加上按秩合并之后整体树的高度几乎被控制在个位数以内。4.4 一个完整的Java模板把上面的思路整理一下我给出一个自己常用的完整模板。它既支持路径压缩也支持按秩合并而且把 find 写成了递归版本——如果程序在深度上可能出问题可以把 find 替换成前面的迭代版本。public class UnionFind { private int[] parent; private int[] rank; private int count; // 记录合并后还剩下多少个集合 public UnionFind(int n) { count 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) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } public boolean isConnected(int x, int y) { return find(x) find(y); } public int getCount() { return count; } }我特意在模板里加了一个 count 字段每次成功合并一个集合就减一。这个字段在不少实际场景里非常有用比如最后想知道还有多少个独立圈子、多少个连通分量直接 getCount() 就行不用再遍历一次 parent 数组去数根。在后面的应用章节里你会看到这个字段的实际价值。5. 边界条件与常见坑我自己踩过的并查集代码虽然短但坑一点都不少。我梳理了几个最常见的每一个都是我在实际写代码时真实踩过的。5.1 初始化时忘了 parent[i] i这是新手最容易犯的错误也是最隐蔽的。如果你不初始化 parent[i] i默认值会是0那么所有节点都会指向0号节点find 操作会得到错误的结果。更麻烦的是在一些特殊的测试用例下代码可能不报错只是结果莫名其妙地不对。我在刚开始写并查集的时候有一次刷题死活过不了就是因为创建 UnionFind 对象之后忘了调用初始化循环。建议在构造方法里完成初始化并且使用前先想清楚从0到n-1的每个下标都要被正确赋值。另外还要注意n 是你元素的总个数如果题目给你的编号是从1开始的比如某些图论题你要么在创建时把 n 加一要么在调用时把编号全部减一这个映射关系一定要想清楚不然很容易越界。5.2 递归版 find 的栈溢出风险在数据规模特别大比如几百万、上千万的时候递归版路径压缩有可能出现栈溢出尤其是在树没有被很好地按秩合并、仍然偏深的情况下。虽然按秩合并能让树高度很低但极端场景下我仍然建议使用迭代版 find反正代码差别也不大。另外还有一个性能细节路径压缩的递归版在最坏情况下会多次访问 parent[x]如果你在 find 里写的不小心比如先递归再赋值顺序错了就起不到压缩效果。算法不是背出来的要理解它的递归栈。// 正确写法先递归到底再逐层返回并压平 public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }5.3 合并方向反了导致 rank 统计不准如果你用的是按秩合并union 里方向千万写反。比如 rank[rootX] rank[rootY] 时你本该把 rootY 挂到 rootX 下面结果写反了把 rootX 挂到 rootY 下面。表面上不算大错但会导致树的高度变大后续 find 效率下降。如果你还维护了 count有可能出现合并了但是数量没减的情况——因为你压根没真正改变根节点。5.4 二维坐标与一维数组的映射在实际应用中并查集处理的往往是节点但很多问题的节点是二维的比如网格上的格子。这时候最常见的做法是把二维坐标转换成唯一的一维编号。通用的做法是index row * cols col其中 cols 是每一行的列数。一旦映射搞错比如用 row * rows 而不是 row * cols那整个并查集结构就乱套了。我见过不止一次因为这种低级错误导致的bug排查过程极其痛苦。假设一个 5 列 4 行的网格坐标 (2, 3) 映射为 2 * 5 3 13。反向映射也很简单row index / colscol index % cols。这里的除法和取模运算在初始化、查询、合并的时候要保持一致。5.5 动态增加节点的问题有些场景下节点数量不是一开始就知道的需要在运行中动态加入新节点。并查集的数组实现方式不适合动态扩容所以有两种解决思路第一种是在初始化时预留足够的空间第二种是改用哈希表来存储 parent 和 rank只在节点真正出现时才创建对应的记录。第二种方案实现起来也不复杂把数组换成 Map 就行唯一要注意的是初始化 parent[x] x 这个动作必须在节点首次出现时执行。6. 并查集的典型应用场景6.1 Kruskal最小生成树算法这应该是并查集最经典的工业级应用了。Kruskal算法求最小生成树的过程是把所有边按权重从小到大排序然后依次取出每一条边判断这条边连接的两个顶点是否已经在同一个连通分量里。如果不在就把它们合并并把这这条边加入生成树。这个判断和合并的过程就是并查集的看家本领。在Kruskal里并查集用的就是 find 和 union 两个操作是教科书级别的配合。// 伪代码展示Kruskal中并查集的使用 ListEdge edges ...; Collections.sort(edges, (a, b) - a.weight - b.weight); UnionFind uf new UnionFind(n); int totalWeight 0; for (Edge e : edges) { if (!uf.isConnected(e.u, e.v)) { uf.union(e.u, e.v); totalWeight e.weight; // 可以记录选中的边 } }这段代码的优美之处在于你不用关心当前的连通分量长什么样只需要问连不连并查集负责在背后把关系维护好。6.2 朋友圈关系与省份数量有一个很常见的问题给定一个矩阵表示人与人之间是否认识求有多少个朋友圈连通分量。这类问题可以直接套用并查集模板。遍历矩阵的上三角遇到两个认识的人就 union最后 getCount() 就是朋友圈数量。很多人第一次觉得并查集有用都是从这个问题开始的。还有一个变体是冗余连接类问题给一个无向图删除一条边让它成为一棵树。这种问题也可以借助并查集——依次把每条边的两个节点 union如果发现某条边连接的两个节点已经连通说明这条边就是冗余的。int[] findRedundantConnection(int[][] edges) { UnionFind uf new UnionFind(edges.length 1); for (int[] e : edges) { if (uf.isConnected(e[0], e[1])) { return e; } uf.union(e[0], e[1]); } return new int[0]; }6.3 等式方程的可满足性LeetCode上的990题给定一组等式和不等式判断它们是否矛盾。比如ab和b!a就是矛盾的。这题用并查集非常直观先把所有等式的两个变量 union 在一起然后再遍历所有不等式看不等号两侧的变量是否已经在同一个集合里如果是说明矛盾。这个应用体现了并查集在处理相等传递性问题上的天然优势。像这种相等关系具有传递性的场景实际上就是并查集的最佳使用场景如果 a 和 b 相等、b 和 c 相等那么 a 和 c 也相等这种传递闭包关系的维护用并查集再合适不过。6.4 动态连通性与网络连接判断在分布式系统、网络拓扑监控等场景中经常需要动态判断两个节点之间的连通状态。当一个节点挂了或者一条链路断了连通性会发生变化。虽然这个场景下图的表示更复杂但并查集作为底层的连通性维护工具依然值得考虑。它可以用于离线处理——比如先把所有断线事件记录下来从最终状态开始倒推把事件反过来处理断线就变成了连线这就是所谓离线并查集的思路。这个技巧在不少算法竞赛题里非常常见实际工程里遇到类似的逆向分析场景也同样适用。7. 一个完整案例二维网格中的岛屿数量为了把前面讲的东西串起来我用一个完整的示例来演示实际编码过程。这个问题是 LeetCode 第200题给定一个由 1陆地和 0水组成的二维网格计算岛屿的数量。一片岛屿是相邻上下左右的陆地连接形成的。这个问题的解法很多DFS 也行。但用并查集来处理能非常清楚地体现二维映射、动态合并、集合计数这几个核心操作。处理步骤遍历网格把所有 1 的格子当作节点。把二维坐标映射成一维编号row * cols col。对每个陆地格子检查它的右方和下方的格子如果也是陆地就把这两个格子 union 起来。统计陆地节点中有多少个根节点这也就是并查集中的 count 被初始化为陆地总数、每合并一次减一的最终结果。public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int rows grid.length; int cols grid[0].length; UnionFind uf new UnionFind(rows * cols); int landCount 0; // 先统计陆地数量并初始化并查集 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { landCount; } } } // 注意需要把count初始化为landCount我这里重新构建 uf new UnionFind(rows * cols); uf.count landCount; // 实际使用时count应该是可访问的或者提供构造参数 int[][] dirs {{0, 1}, {1, 0}}; // 只查右边和下边避免重复 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int idx i * cols j; for (int[] d : dirs) { int ni i d[0]; int nj j d[1]; if (ni 0 ni rows nj 0 nj cols grid[ni][nj] 1) { uf.union(idx, ni * cols nj); } } } } } return uf.getCount(); }这里的并查集构造时 count 初始化为节点总数但实际我们只需要陆地的集合数所以在创建之后把 count 改成陆地的数量。更优雅的做法是提供一个带初始集合数量的构造函数比如UnionFind(int n, int initialCount)或者在初始化遍历时一并做 union。这些细节根据具体需求调整即可。核心的洞察在于水的格子永远不会参与 union但它们仍然占用了数组空间。如果网格很大、水很多这个方案在空间上会有一点浪费。如果追求极致的空间优化可以用哈希表来存储并查集信息只存陆地节点。这也是前面提到的动态增加节点思路的应用场景。8. 关于时间复杂度和一些经验总结很多人看我讲完这些会问并查集的复杂度到底是多少。严格来说同时使用路径压缩和按秩合并的并查集单次 find 或 union 操作的均摊时间复杂度是 O(α(n))这里的 α 是反阿克曼函数。这个函数的增长有多慢呢对所有在物理世界中可能出现的 n它的值都不会超过 4。所以你在实际使用中完全可以把它当作常数时间看待。但要注意这指的是均摊复杂度不是单次最坏复杂度。路径压缩有一种性质叫均摊意思是多次操作叠加起来的总代价很低但某一次单独操作可能还是会扫描比较长的路径。好在实际工程中这个差别几乎感知不到。还有一点经验上的建议在正式项目里用并查集优先抄一个标准、完整、经过充分测试的模板不要每次都临时写。这个模板要支持 find、union、isConnected、getCount 这些基本操作并且初始化、秩的处理、路径压缩的逻辑都要正确。我不建议在代码里混合不同版本的写法比如用了路径压缩却忘了按秩合并或者 union 方向写反但这种错误是编译发现不了的。另一个建议是并查集虽然本身是通用的数据结构但在真实项目里很少会有直接让你就是并查集的需求更多的时候你需要做的是把业务场景抽象成并查集。抽象的关键在于弄清楚两点第一什么对象是节点第二什么事件是合并。想明白这两个问题代码只是顺手的事。比如在社交网络里节点是用户合并事件是两个用户互相成为好友在网络监控里节点是设备合并事件是两台设备建立连接在图像处理里节点是像素合并事件是两个像素颜色相似。这种抽象的转换能力比背熟模板更值钱。我建议你遇到一个新问题的时候先别急着写代码花几分钟想想这个问题是否能拆解成节点合并如果答案是肯定的那大概率就是并查集的菜。并查集有一套简洁的美。它逻辑上是一个复杂的图论连通性问题物理上却只需要两个数组和二三十行代码就能做到接近常数时间的查询与合并。这种以小博大的设计是很多算法都比不上的。希望这篇文章能把它的思想和代码实现都讲透让你在需要的时候能第一时间想到它、用对它。