尧图网页设计 
并查集这个东西在很多人的印象里是个“学了就忘、忘了再学”的尴尬存在——代码明明不到二十行但每次真要写的时候还是会纠结路径压缩到底怎么压按秩合并是比大小还是比深度更关键的是遇到实际问题时怎么判断“这题能用并查集”前阵子我在做一个社交关系聚类的小项目需要反复判断两个用户是否属于同一个可达圈子数据量到了百万级别才真正体会到这个高阶数据结构能有多能打。这篇文章我打算把并查集讲透。不是简单贴一个模板让你背而是从它解决的问题出发把为什么要用数组、为什么要路径压缩、为什么要按秩合并、复杂度为什么近似常数、实战中能怎么用、踩过哪些坑一层层拆开讲。不管你是刚开始接触高级数据结构的新手还是已经背熟了模板但不太会用的人这篇内容应该都能给你一些新东西。1. 并查集到底在解决什么问题一类“动态连通性”需求1.1 一个直觉例子社交网络里的“圈子”先设想一个场景。你有 n 个用户一开始谁也不认识谁。每次给你一条信息说“用户 a 和用户 b 成为了好友”好友关系是可以传递的——也就是说如果 a 认识 bb 认识 c那么 a 和 c 在某种意义上处于同一个“圈子”里。现在你需要随时回答用户 x 和用户 y 是不是在同一个圈子里这就是典型的动态连通性问题。注意“动态”两个字意味着关系是不断增加的而不是一开始就给你一张完整的图。如果图是静态的你可以先用 DFS 或 BFS 预处理出连通分量之后每次查询 O(1) 回答。但关系不断新增你不可能每次加一条边就全图重扫一遍那就需要一种能“边加边查”的结构。并查集就是为这种需求量身定做的。它不关心两个用户之间的具体路径是什么样只关心“最终能不能连通”。好比你在一个陌生的城市问路你只需要知道某个区域能不能通过步行到达另一个区域而不需要知道每一步具体走哪条街。1.2 两个核心操作合并与查询并查集Disjoint Set Union简称 DSU也有叫 Union-Find 的只支持两类操作find(x)找到 x 所在的集合代表元素也就是集合的“根”。union(x, y)把 x 和 y 所在的两个集合合并成一个。名字里的 Disjoint 点出了一个重要性质任意时刻每个元素只属于一个集合集合之间互不相交。所以并查集维护的是一组“不相交集合”的合并与归属查询。回到社交网络的例子union(a, b)对应“a 和 b 成为好友”find(x) find(y)对应“x 和 y 在同一个圈子里”。就这么简单。这里有一个新手很容易忽略的点并查集的查找对象是“元素”而不是“关系”。每个元素一开始是自己所在集合的根随着不断合并越来越多的元素被“挂”到同一个根下面。集合的形态是一棵多叉树根就是集合的标识。1.3 如何判断一个需求是否适合用并查集我在实际项目里判断一个问题能不能用并查集一般看三个特征只关心归属不关心路径。如果问题明确要求输出两个节点之间的具体路径并查集做不了那是 DFS/BFS 或者最短路的事。操作只有“合并”和“查询”两类。注意并查集天然不支持“拆分集合”。如果问题里有分离操作普通并查集直接不行得考虑可撤销版本或者其他结构。能离线处理。有些看似需要删除的操作如果允许先把所有删除处理完再反向加回去并查集仍然能胜任。这个技巧在后面实战部分会详细讲。把握住这三条比背一百道题都管用。很多所谓的“并查集难题”本质上都是在问你怎么把题目中的操作转化成合并和查询。2. 从零手写并查集从朴素实现到两大优化2.1 用数组表达“森林”parent 指针的意义并查集的底层结构极其简单一个一维数组就够了int parent[N];parent[i]表示元素 i 的父节点是谁。如果parent[i] i说明 i 是自己所在集合的根节点。一开始每个元素都是独立的集合所以初始化的代码是for (int i 0; i n; i) { parent[i] i; }这整个结构就是一个森林——每个集合是一棵树根是集合的代表。不理解为什么用树的人通常会卡在“集合怎么用树表示”这个问题上。换个角度想一个集合里总得有个“话事人”当作标识吧树形结构的好处是只要不断沿着父指针往上找最终一定会到达根这个根就是集合标识。用树形结构表示集合看起来多此一举——直接用集合编号不行吗不行因为你不知道预先会有多少个集合也不知道哪些集合会被合并。树形结构让合并操作变成了简单的改指针这才是精髓。2.2 朴素实现find 与 unite 的写法先写一个最朴素的版本虽然慢但逻辑最清晰// 查找 x 所属集合的根 int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; } // 合并 x 和 y 所在的集合 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 把 x 的根挂到 y 的根下面 } }注意unite这个名字很多人写成union但union在 C 里是关键字所以竞赛代码里一般用unite或者merge。朴素的 find 在最坏情况下会退化到什么程度如果每次合并都是把一个很深的树根挂到另一个根下面比如依次unite(1,2)、unite(2,3)、unite(3,4)……不加任何优化的话树会变成一条链。这时find(1)需要一路走到链尾复杂度 O(n)。当有 n 次这样的查询时总复杂度 O(n²)数据量稍微一大就爆了。2.3 路径压缩把树“拍扁”的关键一步既然 find 的瓶颈在于链太长那就想办法让树变矮。路径压缩的思路很直接当我在找 x 的根时一路上经过的所有节点它们的根其实都是同一个。那不如直接把这条路径上所有节点的父指针都改成根节点。递归写法非常经典简洁到让人怀疑是不是写错了int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }这行parent[x] find(parent[x])做的事就是先递归找到根然后把 x 直接挂在根下面。整个递归回溯过程中路径上每个节点都会被挂到根上树被“拍扁”了。迭代版本稍微绕一点但避免了递归开销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; }第一次循环找到根第二次循环把路径上的节点全部指向根。思路和递归版一模一样只是顺序不同。这里要留意一个很多人忽略的细节路径压缩并不会让树高立刻变成 1它只压缩“查询过”的路径。现在把一棵树的叶子查了一次叶子直接挂到根上但其他分支的深度没变。真正让整体树高保持稳定的是另一个优化——按秩合并。2.4 按秩合并从源头控制树的高度按秩合并Union by Rank的核心思想合并两棵树时总是把矮的树挂到高的树下面避免树高无脑增长。这里的“秩”rank通常指树的高度上界。为了维护这个信息需要开一个rank数组初始都是 0表示只有一个节点的树高度为 0。int parent[N]; int rank_[N]; // 注意rank 在 C 里和 std::rank 有冲突很多人用 rank_ void unite(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[rootY] rootX; rank_[rootX]; } }两棵高度相同的树合并无论谁挂到谁下面新的树高度都会比原来多 1所以需要给新根的秩加 1。如果高度不同矮的挂到高的下面总高度不变秩自然也不用变。这里有个误区加了路径压缩之后rank 数组就不再等于真实的树高了它只是一个“上界”。但这没关系按秩合并不需要精确的树高它只需要一个足够好的“相对高度”来指导合并方向。你甚至可以按集合大小合并效果同样不错int size_[N]; // 记录集合大小 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (size_[rootX] size_[rootY]) swap(rootX, rootY); parent[rootY] rootX; size_[rootX] size_[rootY]; }按大小合并的好处是顺带维护了集合元素个数后面要统计连通块大小时特别好用。2.5 完整代码与初始化要点把上面的内容整合成一个可以直接抄的模板class DSU { private: vectorint parent, rank_; public: DSU(int n) { parent.resize(n); rank_.resize(n, 0); for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(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]; } } bool connected(int x, int y) { return find(x) find(y); } };初始化时一定要把 parent[i] 设置成 i这一步漏了后面全乱套。我之前见过一个项目里有人忘了初始化直接调 find结果每个元素都指向 0所有查询都返回 true排查了半天才发现是初始化问题。3. 复杂度背后的真相为什么两个优化缺一不可3.1 四种实现方式的复杂度对比很多资料直接给出结论路径压缩 按秩合并后单次操作的均摊复杂度是 O(α(n))α 是反阿克曼函数增长极其缓慢在现实数据规模下可以认为是常数。但如果你只用其中一个优化呢实现方式find 均摊复杂度说明朴素实现O(n)最坏情况下树退化成一条链只做路径压缩O(log n)整体表现不错但单独分析更复杂只做按秩合并O(log n)树高被严格控制在 log n非常稳定路径压缩 按秩合并O(α(n))理论最优组合近似常数只做路径压缩而不按秩合并且在某些特殊操作序列下仍然能达到 O(log n) 的均摊复杂度但理解起来比较费劲。普通工程场景下两个优化一起写没有任何坏处代码量也就多三四行所以我从来都是两个一起写。3.2 α(n) 是什么一个几乎不增长的“常数”α(n) 是阿克曼函数的反函数。阿克曼函数本身增长快得离谱A(4, 2) 已经是一个天文数字级的数了。反函数的意思就是α(n) 要达到一个较大的值n 得大到难以想象。举个例子α(10^80) 大概是 4——你把整个宇宙中的原子总数作为 nα(n) 也才是个位数。所以在实际工程中把并查集单次操作当成 O(1) 没有任何问题。但这里要强调一个容易被误解的点O(α(n)) 是“均摊复杂度”不是“单次最坏复杂度”。极端情况下某一次 find 操作仍然可能要遍历很多节点只不过这一系列操作的总代价是被控制住了。3.3 路径压缩与按秩合并为什么是互补的我刚开始学的时候一直没想明白既然路径压缩能把树拍扁按秩合并还有必要吗答案是路径压缩的“拍扁”是被动的它只在查询路径上的节点时生效。如果一个集合里有多棵子树你只压缩了查询经过的那一条路径其他子树的深度并没有变。如果后续频繁查询的不是刚才那条路径那些深节点依然很深。按秩合并则是在“源头”上做了控制每次合并都尽量把矮树挂到高树下让整棵树的高度增长尽可能慢。它的作用不是立刻把树拍扁而是防止树长得太歪。一个是事后补救一个是源头预防两者结合才让复杂度达到令人发指的 O(α(n))。这里还有一个工程上的小细节因为按秩合并已经保证了树高是 O(log n)所以即使某些极端情况下路径压缩来不及生效find 的最坏复杂度也只是 O(log n)不会退化到 O(n)。这也是我为什么强烈建议两个优化一起写的原因——你得到的不仅是理论最优还有更稳定的实际表现。4. 经典实战应用从最小生成树到离线倒序4.1 Kruskal 算法判断成环的核心工具Kruskal 是最小生成树MST的经典算法它和并查集的配合堪称天作之合。算法的流程相信大家都熟悉把所有边按权重从小到大排序。依次取出边 (u, v)。如果 u 和 v 不在同一个集合里就选这条边并合并 u 和 v 的集合。如果已经在同一个集合说明这条边会形成环跳过。重复直到选出 n-1 条边。如果不加最后的并查集判断你怎么知道某条边会不会形成环如果已经选了一些边再选 (u, v)只要 u 和 v 已经连通就一定会形成环。这里“判断两个点是否连通”就是并查集的看家本领。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int total 0; int cnt 0; for (auto e : edges) { if (!dsu.connected(e.u, e.v)) { dsu.unite(e.u, e.v); total e.w; cnt; if (cnt n - 1) break; } } return total; }时间复杂度 O(m log m)主要瓶颈在排序上并查集部分接近 O(1)。如果不用并查集用 BFS 每次判断连通性复杂度直接多一个因子 O(m)在大图上根本跑不动。4.2 二维网格连通块统计LeetCode 上有一类题叫“岛屿数量”给一个二维网格1 表示陆地0 表示水问有多少个连通的岛屿。常规解法是 BFS/DFS每遇到一个未访问的 1 就做一次搜索。但用并查集同样能做思路是把二维坐标映射成一维索引int id(int i, int j, int m) { return i * m j; }遍历每个格子如果是陆地就检查它的右边和下面的格子如果也是陆地就合并这两个格子所在集合。最后统计有多少个陆地格子的 root 是它自己就是岛屿数量。int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int n grid.size(), m grid[0].size(); DSU dsu(n * m); int dx[] {1, 0}; // 只查右边和下面避免重复合并 int dy[] {0, 1}; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 0) continue; for (int k 0; k 2; k) { int ni i dx[k], nj j dy[k]; if (ni n nj m grid[ni][nj] 1) { dsu.unite(id(i, j, m), id(ni, nj, m)); } } } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 dsu.find(id(i, j, m)) id(i, j, m)) { ans; } } } return ans; }这种问题的转化核心是“把二维问题压成一维”很多网格类并查集题目都是这个套路。相比 BFS并查集的好处是当你还在不断动态加陆地时它能边加边维护。4.3 离线倒序处理把“删边”变成“加边”这是并查集最经典的进阶技巧也是我认为它真正区别于其他数据结构的地方。假设现在有一个无向图依次执行 q 次操作每次是“删除一条边”或者“询问两个点是否连通”。如果你顺着做每次删边后都要重新维护连通性而并查集不支持删边直接卡住。但如果你倒过来看呢最后的图就是所有删除操作都执行完后的状态然后从最后一个操作往前面处理最后一个操作如果是“删边”反过来就是“加边”——这正好是并查集的强项。最后一个操作如果是“询问”直接 find 回答即可。这个思想叫“离线倒序”核心是改变处理顺序以匹配数据结构的能力。理解它有个关键前提必须先知道所有操作序列不能边输入边处理。我记得有一次做一个项目需求用户会动态关闭服务器之间的连接通道同时需要随时确认两个服务当前是否还能通信。一开始顺着做怎么也做不顺后来想到离线倒序把流程调了个头代码量直接砍半。这种“把删除操作积攒起来反过来当作插入”的思路在并查集题目里出现频率极高。4.4 带权并查集从连通性到“关系维护”普通并查集只回答“是否在一个集合”但有些问题要求知道“集合内元素之间的关系”。这就需要带权并查集在维护父子关系的同时维护每个节点到父节点的某种“权值”。经典题目是“食物链”POJ 1182动物分为三类A 吃 BB 吃 CC 吃 A。现在给你若干条件描述两个动物是同类还是捕食关系需要判断哪些条件是矛盾的。解法是用并查集维护每只动物和根节点的关系用weight[x]表示 x 与 parent[x] 的关系0 表示同类1 表示 x 吃 parent[x]2 表示 parent[x] 吃 x。带权并查集的 find 需要同步更新权值int find(int x) { if (parent[x] x) return x; int px parent[x]; int root find(px); weight[x] (weight[x] weight[px]) % 3; parent[x] root; return root; }注意这里必须先保存px parent[x]再递归然后用weight[px]来更新weight[x]。递归回来后parent[x]已经被改成根了如果这时候再去访问parent[x]的旧值就会出错。这是带权并查集最容易写错的地方我在这里栽过不止一次。合并时同样要确定权值的方向公式经过推导可以得到如果 x 对 y 的关系是 dd0 同类d1 表示 x 吃 y合并 find(x) 到 find(y) 时weight[rootX] (d weight[y] - weight[x] 3) % 3;这个公式别死记每次写的时候推导一遍更稳妥假设 rootX 和 rootY 分别为两个集合的根目标是让 x 到 rootY 的权值和 y 到 rootY 的权值满足给定关系。从 x 出发经过 weight[x] 到 rootX再经过 weight[rootX] 到 rootY总权值应该等于 d 加权值 y 到 rootY 的路径补全。多画几张图就能理解。带权并查集的价值在于你能在维护连通性的同时维护集合内部元素之间的代数关系距离、差值、相对顺序等。我后来处理“银河英雄传说”那道题时需要维护每个战舰到队首的距离用的就是同一个套路只是权值从模 3 关系变成了实际距离累加。5. 手写实现时的常见坑与排查经验5.1 find 的递归写法小心栈溢出路径压缩的递归写法虽然简洁但在极端情况下有栈溢出风险。当树高达到数万甚至数十万时递归深度会超过默认栈限制程序直接崩溃。我在一个百万级节点的并查集上测过如果只按秩合并而不做路径压缩树高上限是 log n 级别的递归没问题。但如果某些地方写错了树退化成链递归深度就是节点数栈不爆才怪。如果你在项目里担心这点用迭代版 find 更安全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; }这个版本没有任何递归性能稳定推荐在工程代码里使用。竞赛里用递归写是因为代码短、看起来优雅但真要长期维护迭代版是更稳妥的选择。5.2 合并方向swap 调用的效果写 unite 时最简单的写法是if (rank_[rootX] rank_[rootY]) { parent[rootX] rootY; } else { parent[rootY] rootX; }相当于默认让 rootX 作为新根除非 rootX 的秩比 rootY 小。但如果换一种思路先做 swap 再统一处理代码会更清晰if (rank_[rootX] rank_[rootY]) swap(rootX, rootY); parent[rootY] rootX; if (rank_[rootX] rank_[rootY]) rank_[rootX];swap 之后rootX 一定是秩较大的那一个后续逻辑统一处理即可不容易漏分支。两段代码等价但 swap 版本我私心推荐因为少了 else 分支嵌套降低了写错的可能。5.3 初始化顺序与“孤岛”问题并查集最常见的隐性 bug 就是初始化遗漏。比如你只初始化了部分节点后面的节点 parent[i] 是垃圾值find 会指向任意内存导致查询结果完全随机。另一个容易忽略的问题是“孤立节点”。如果你的数据中有节点自始至终没有参与任何合并它的 parent 始终等于自己find 返回它自己这是正确的。但如果你在写代码时假设“所有节点最终都合并到同一个集合”那统计结果就会出问题。所以写并查集时我习惯在构造完对象后立刻把所有 parent[i] 初始化好并且写一个测试用例专门验证“没有合并过的节点表现正常”。5.4 带权并查集的方向约定我踩过的坑带权并查集最难的不是 find 的更新而是合并时的方向约定。我踩过的坑是合并两个集合时把 rootX 和 rootY 的顺序搞反导致所有后续关系全部偏置。调试这类问题最有效的方法是小规模数据逐步模拟构造 3-4 个节点手动合并几次每一步都打印出每个节点的 parent 和 weight看看数据的相对关系是否符合预期。不要在大数据上瞎试那只会浪费时间。还有一个经验是给 weight 数组初始化为 0 一定要做因为 0 通常表示“与自身同类”的默认关系。如果忘记初始化后续取模运算得到的结果毫无意义。6. 进阶变体可撤销并查集与维护额外信息6.1 可撤销并查集支持回滚的版本普通并查集不支持“撤销最后一次合并”。但在一些搜索算法和离线问题里你需要在 DFS 回溯时恢复到之前的状态这时候就需要可撤销并查集。实现思路并不复杂因为每次合并实际上只修改了两个数组元素parent 和 rank只要把修改前的值记录到一个栈里回滚时弹栈还原即可。但这里有一个关键要求可撤销并查集不能用路径压缩。原因很直接路径压缩会修改路径上很多节点的 parent 指针万一要回滚栈里得存一整个路径的信息复杂度就失控了。所以可撤销版本只保留按秩合并这样单次合并只改了常数个位置回滚成本是 O(1)。struct Change { int pos; int oldVal; }; vectorChange history; void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { history.push_back({-1, -1}); // 空操作标记 return; } if (rank_[rootX] rank_[rootY]) swap(rootX, rootY); history.push_back({rootY, parent[rootY]}); parent[rootY] rootX; if (rank_[rootX] rank_[rootY]) { history.push_back({rootX, rank_[rootX]}); rank_[rootX]; } } void rollback() { Change c history.back(); history.pop_back(); if (c.pos ! -1) parent[c.pos] c.oldVal; if (!history.empty()) { c history.back(); history.pop_back(); if (c.pos ! -1) rank_[c.pos] c.oldVal; } }这个变体在“动态图问题”里特别有用比如判断一个图是否是二分图的某个动态版本处理到一半要回退用可撤销并查集就能高效维护。6.2 维护集合大小与附加信息有时候不仅要知道两个元素是否同集合还要知道某个集合里有多少元素。按大小合并天然支持这个size_[rootX] size_[rootY];除了大小你还可以在根节点上维护任何你关心的集合级信息比如集合的总和、最大最小值。合并时只需要把两个根的信息合并sum[rootX] sum[rootY]; maxVal[rootX] max(maxVal[rootX], maxVal[rootY]);这相当于把并查集变成了一个简易的“集合信息维护器”。我在处理一些图聚类时会用并查集维护聚类大小和中心点坐标的累加和最后统一算平均值逻辑非常简单。6.3 什么时候不该用并查集讲到这里我想多分享一些我自己的体会。并查集虽然强大但它的能力边界也很明确。需要动态删边时如果问题在线不能预知后续操作并查集做不了得上 LCTLink-Cut Tree这类更重的结构。需要输出具体连通路径时并查集只告诉你“通不通”不告诉你“怎么通”此时维护图结构或做搜索才是正确的。需要维护集合内部顺序关系时并查集只适用于等价关系自反、对称、传递如果你要维护的是偏序关系它无能为力。需要合并的规模不平衡时比如每次合并前要检查大量不同集合之间的条件关系并查集虽然能快速合并但你仍然需要其他数据结构辅助枚举和筛选。所以在实际工程和刷题中我习惯先问三个问题操作是合并还是删除查询是判连通还是求路径数据范围允不允许离线这些问题想清楚再动手写代码基本不会走弯路。并查集最让我欣赏的一点是它把“群体归属”这种看似抽象的概念变成了几个指针操作。几十行代码复杂度接近常数却能在百万甚至千万级的动态场景下稳定工作。有时候复杂的业务问题抽丝剥茧后底层就是一个并查集——这也是我为什么一直建议每个做算法和做工程的开发者都花心思把这个结构吃透的原因。 并查集从原理到实战：路径压缩、按秩合并与动态连通性全解析
并查集这个东西在很多人的印象里是个“学了就忘、忘了再学”的尴尬存在——代码明明不到二十行但每次真要写的时候还是会纠结路径压缩到底怎么压按秩合并是比大小还是比深度更关键的是遇到实际问题时怎么判断“这题能用并查集”前阵子我在做一个社交关系聚类的小项目需要反复判断两个用户是否属于同一个可达圈子数据量到了百万级别才真正体会到这个高阶数据结构能有多能打。这篇文章我打算把并查集讲透。不是简单贴一个模板让你背而是从它解决的问题出发把为什么要用数组、为什么要路径压缩、为什么要按秩合并、复杂度为什么近似常数、实战中能怎么用、踩过哪些坑一层层拆开讲。不管你是刚开始接触高级数据结构的新手还是已经背熟了模板但不太会用的人这篇内容应该都能给你一些新东西。1. 并查集到底在解决什么问题一类“动态连通性”需求1.1 一个直觉例子社交网络里的“圈子”先设想一个场景。你有 n 个用户一开始谁也不认识谁。每次给你一条信息说“用户 a 和用户 b 成为了好友”好友关系是可以传递的——也就是说如果 a 认识 bb 认识 c那么 a 和 c 在某种意义上处于同一个“圈子”里。现在你需要随时回答用户 x 和用户 y 是不是在同一个圈子里这就是典型的动态连通性问题。注意“动态”两个字意味着关系是不断增加的而不是一开始就给你一张完整的图。如果图是静态的你可以先用 DFS 或 BFS 预处理出连通分量之后每次查询 O(1) 回答。但关系不断新增你不可能每次加一条边就全图重扫一遍那就需要一种能“边加边查”的结构。并查集就是为这种需求量身定做的。它不关心两个用户之间的具体路径是什么样只关心“最终能不能连通”。好比你在一个陌生的城市问路你只需要知道某个区域能不能通过步行到达另一个区域而不需要知道每一步具体走哪条街。1.2 两个核心操作合并与查询并查集Disjoint Set Union简称 DSU也有叫 Union-Find 的只支持两类操作find(x)找到 x 所在的集合代表元素也就是集合的“根”。union(x, y)把 x 和 y 所在的两个集合合并成一个。名字里的 Disjoint 点出了一个重要性质任意时刻每个元素只属于一个集合集合之间互不相交。所以并查集维护的是一组“不相交集合”的合并与归属查询。回到社交网络的例子union(a, b)对应“a 和 b 成为好友”find(x) find(y)对应“x 和 y 在同一个圈子里”。就这么简单。这里有一个新手很容易忽略的点并查集的查找对象是“元素”而不是“关系”。每个元素一开始是自己所在集合的根随着不断合并越来越多的元素被“挂”到同一个根下面。集合的形态是一棵多叉树根就是集合的标识。1.3 如何判断一个需求是否适合用并查集我在实际项目里判断一个问题能不能用并查集一般看三个特征只关心归属不关心路径。如果问题明确要求输出两个节点之间的具体路径并查集做不了那是 DFS/BFS 或者最短路的事。操作只有“合并”和“查询”两类。注意并查集天然不支持“拆分集合”。如果问题里有分离操作普通并查集直接不行得考虑可撤销版本或者其他结构。能离线处理。有些看似需要删除的操作如果允许先把所有删除处理完再反向加回去并查集仍然能胜任。这个技巧在后面实战部分会详细讲。把握住这三条比背一百道题都管用。很多所谓的“并查集难题”本质上都是在问你怎么把题目中的操作转化成合并和查询。2. 从零手写并查集从朴素实现到两大优化2.1 用数组表达“森林”parent 指针的意义并查集的底层结构极其简单一个一维数组就够了int parent[N];parent[i]表示元素 i 的父节点是谁。如果parent[i] i说明 i 是自己所在集合的根节点。一开始每个元素都是独立的集合所以初始化的代码是for (int i 0; i n; i) { parent[i] i; }这整个结构就是一个森林——每个集合是一棵树根是集合的代表。不理解为什么用树的人通常会卡在“集合怎么用树表示”这个问题上。换个角度想一个集合里总得有个“话事人”当作标识吧树形结构的好处是只要不断沿着父指针往上找最终一定会到达根这个根就是集合标识。用树形结构表示集合看起来多此一举——直接用集合编号不行吗不行因为你不知道预先会有多少个集合也不知道哪些集合会被合并。树形结构让合并操作变成了简单的改指针这才是精髓。2.2 朴素实现find 与 unite 的写法先写一个最朴素的版本虽然慢但逻辑最清晰// 查找 x 所属集合的根 int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; } // 合并 x 和 y 所在的集合 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 把 x 的根挂到 y 的根下面 } }注意unite这个名字很多人写成union但union在 C 里是关键字所以竞赛代码里一般用unite或者merge。朴素的 find 在最坏情况下会退化到什么程度如果每次合并都是把一个很深的树根挂到另一个根下面比如依次unite(1,2)、unite(2,3)、unite(3,4)……不加任何优化的话树会变成一条链。这时find(1)需要一路走到链尾复杂度 O(n)。当有 n 次这样的查询时总复杂度 O(n²)数据量稍微一大就爆了。2.3 路径压缩把树“拍扁”的关键一步既然 find 的瓶颈在于链太长那就想办法让树变矮。路径压缩的思路很直接当我在找 x 的根时一路上经过的所有节点它们的根其实都是同一个。那不如直接把这条路径上所有节点的父指针都改成根节点。递归写法非常经典简洁到让人怀疑是不是写错了int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }这行parent[x] find(parent[x])做的事就是先递归找到根然后把 x 直接挂在根下面。整个递归回溯过程中路径上每个节点都会被挂到根上树被“拍扁”了。迭代版本稍微绕一点但避免了递归开销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; }第一次循环找到根第二次循环把路径上的节点全部指向根。思路和递归版一模一样只是顺序不同。这里要留意一个很多人忽略的细节路径压缩并不会让树高立刻变成 1它只压缩“查询过”的路径。现在把一棵树的叶子查了一次叶子直接挂到根上但其他分支的深度没变。真正让整体树高保持稳定的是另一个优化——按秩合并。2.4 按秩合并从源头控制树的高度按秩合并Union by Rank的核心思想合并两棵树时总是把矮的树挂到高的树下面避免树高无脑增长。这里的“秩”rank通常指树的高度上界。为了维护这个信息需要开一个rank数组初始都是 0表示只有一个节点的树高度为 0。int parent[N]; int rank_[N]; // 注意rank 在 C 里和 std::rank 有冲突很多人用 rank_ void unite(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[rootY] rootX; rank_[rootX]; } }两棵高度相同的树合并无论谁挂到谁下面新的树高度都会比原来多 1所以需要给新根的秩加 1。如果高度不同矮的挂到高的下面总高度不变秩自然也不用变。这里有个误区加了路径压缩之后rank 数组就不再等于真实的树高了它只是一个“上界”。但这没关系按秩合并不需要精确的树高它只需要一个足够好的“相对高度”来指导合并方向。你甚至可以按集合大小合并效果同样不错int size_[N]; // 记录集合大小 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (size_[rootX] size_[rootY]) swap(rootX, rootY); parent[rootY] rootX; size_[rootX] size_[rootY]; }按大小合并的好处是顺带维护了集合元素个数后面要统计连通块大小时特别好用。2.5 完整代码与初始化要点把上面的内容整合成一个可以直接抄的模板class DSU { private: vectorint parent, rank_; public: DSU(int n) { parent.resize(n); rank_.resize(n, 0); for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(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]; } } bool connected(int x, int y) { return find(x) find(y); } };初始化时一定要把 parent[i] 设置成 i这一步漏了后面全乱套。我之前见过一个项目里有人忘了初始化直接调 find结果每个元素都指向 0所有查询都返回 true排查了半天才发现是初始化问题。3. 复杂度背后的真相为什么两个优化缺一不可3.1 四种实现方式的复杂度对比很多资料直接给出结论路径压缩 按秩合并后单次操作的均摊复杂度是 O(α(n))α 是反阿克曼函数增长极其缓慢在现实数据规模下可以认为是常数。但如果你只用其中一个优化呢实现方式find 均摊复杂度说明朴素实现O(n)最坏情况下树退化成一条链只做路径压缩O(log n)整体表现不错但单独分析更复杂只做按秩合并O(log n)树高被严格控制在 log n非常稳定路径压缩 按秩合并O(α(n))理论最优组合近似常数只做路径压缩而不按秩合并且在某些特殊操作序列下仍然能达到 O(log n) 的均摊复杂度但理解起来比较费劲。普通工程场景下两个优化一起写没有任何坏处代码量也就多三四行所以我从来都是两个一起写。3.2 α(n) 是什么一个几乎不增长的“常数”α(n) 是阿克曼函数的反函数。阿克曼函数本身增长快得离谱A(4, 2) 已经是一个天文数字级的数了。反函数的意思就是α(n) 要达到一个较大的值n 得大到难以想象。举个例子α(10^80) 大概是 4——你把整个宇宙中的原子总数作为 nα(n) 也才是个位数。所以在实际工程中把并查集单次操作当成 O(1) 没有任何问题。但这里要强调一个容易被误解的点O(α(n)) 是“均摊复杂度”不是“单次最坏复杂度”。极端情况下某一次 find 操作仍然可能要遍历很多节点只不过这一系列操作的总代价是被控制住了。3.3 路径压缩与按秩合并为什么是互补的我刚开始学的时候一直没想明白既然路径压缩能把树拍扁按秩合并还有必要吗答案是路径压缩的“拍扁”是被动的它只在查询路径上的节点时生效。如果一个集合里有多棵子树你只压缩了查询经过的那一条路径其他子树的深度并没有变。如果后续频繁查询的不是刚才那条路径那些深节点依然很深。按秩合并则是在“源头”上做了控制每次合并都尽量把矮树挂到高树下让整棵树的高度增长尽可能慢。它的作用不是立刻把树拍扁而是防止树长得太歪。一个是事后补救一个是源头预防两者结合才让复杂度达到令人发指的 O(α(n))。这里还有一个工程上的小细节因为按秩合并已经保证了树高是 O(log n)所以即使某些极端情况下路径压缩来不及生效find 的最坏复杂度也只是 O(log n)不会退化到 O(n)。这也是我为什么强烈建议两个优化一起写的原因——你得到的不仅是理论最优还有更稳定的实际表现。4. 经典实战应用从最小生成树到离线倒序4.1 Kruskal 算法判断成环的核心工具Kruskal 是最小生成树MST的经典算法它和并查集的配合堪称天作之合。算法的流程相信大家都熟悉把所有边按权重从小到大排序。依次取出边 (u, v)。如果 u 和 v 不在同一个集合里就选这条边并合并 u 和 v 的集合。如果已经在同一个集合说明这条边会形成环跳过。重复直到选出 n-1 条边。如果不加最后的并查集判断你怎么知道某条边会不会形成环如果已经选了一些边再选 (u, v)只要 u 和 v 已经连通就一定会形成环。这里“判断两个点是否连通”就是并查集的看家本领。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int total 0; int cnt 0; for (auto e : edges) { if (!dsu.connected(e.u, e.v)) { dsu.unite(e.u, e.v); total e.w; cnt; if (cnt n - 1) break; } } return total; }时间复杂度 O(m log m)主要瓶颈在排序上并查集部分接近 O(1)。如果不用并查集用 BFS 每次判断连通性复杂度直接多一个因子 O(m)在大图上根本跑不动。4.2 二维网格连通块统计LeetCode 上有一类题叫“岛屿数量”给一个二维网格1 表示陆地0 表示水问有多少个连通的岛屿。常规解法是 BFS/DFS每遇到一个未访问的 1 就做一次搜索。但用并查集同样能做思路是把二维坐标映射成一维索引int id(int i, int j, int m) { return i * m j; }遍历每个格子如果是陆地就检查它的右边和下面的格子如果也是陆地就合并这两个格子所在集合。最后统计有多少个陆地格子的 root 是它自己就是岛屿数量。int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int n grid.size(), m grid[0].size(); DSU dsu(n * m); int dx[] {1, 0}; // 只查右边和下面避免重复合并 int dy[] {0, 1}; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 0) continue; for (int k 0; k 2; k) { int ni i dx[k], nj j dy[k]; if (ni n nj m grid[ni][nj] 1) { dsu.unite(id(i, j, m), id(ni, nj, m)); } } } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 dsu.find(id(i, j, m)) id(i, j, m)) { ans; } } } return ans; }这种问题的转化核心是“把二维问题压成一维”很多网格类并查集题目都是这个套路。相比 BFS并查集的好处是当你还在不断动态加陆地时它能边加边维护。4.3 离线倒序处理把“删边”变成“加边”这是并查集最经典的进阶技巧也是我认为它真正区别于其他数据结构的地方。假设现在有一个无向图依次执行 q 次操作每次是“删除一条边”或者“询问两个点是否连通”。如果你顺着做每次删边后都要重新维护连通性而并查集不支持删边直接卡住。但如果你倒过来看呢最后的图就是所有删除操作都执行完后的状态然后从最后一个操作往前面处理最后一个操作如果是“删边”反过来就是“加边”——这正好是并查集的强项。最后一个操作如果是“询问”直接 find 回答即可。这个思想叫“离线倒序”核心是改变处理顺序以匹配数据结构的能力。理解它有个关键前提必须先知道所有操作序列不能边输入边处理。我记得有一次做一个项目需求用户会动态关闭服务器之间的连接通道同时需要随时确认两个服务当前是否还能通信。一开始顺着做怎么也做不顺后来想到离线倒序把流程调了个头代码量直接砍半。这种“把删除操作积攒起来反过来当作插入”的思路在并查集题目里出现频率极高。4.4 带权并查集从连通性到“关系维护”普通并查集只回答“是否在一个集合”但有些问题要求知道“集合内元素之间的关系”。这就需要带权并查集在维护父子关系的同时维护每个节点到父节点的某种“权值”。经典题目是“食物链”POJ 1182动物分为三类A 吃 BB 吃 CC 吃 A。现在给你若干条件描述两个动物是同类还是捕食关系需要判断哪些条件是矛盾的。解法是用并查集维护每只动物和根节点的关系用weight[x]表示 x 与 parent[x] 的关系0 表示同类1 表示 x 吃 parent[x]2 表示 parent[x] 吃 x。带权并查集的 find 需要同步更新权值int find(int x) { if (parent[x] x) return x; int px parent[x]; int root find(px); weight[x] (weight[x] weight[px]) % 3; parent[x] root; return root; }注意这里必须先保存px parent[x]再递归然后用weight[px]来更新weight[x]。递归回来后parent[x]已经被改成根了如果这时候再去访问parent[x]的旧值就会出错。这是带权并查集最容易写错的地方我在这里栽过不止一次。合并时同样要确定权值的方向公式经过推导可以得到如果 x 对 y 的关系是 dd0 同类d1 表示 x 吃 y合并 find(x) 到 find(y) 时weight[rootX] (d weight[y] - weight[x] 3) % 3;这个公式别死记每次写的时候推导一遍更稳妥假设 rootX 和 rootY 分别为两个集合的根目标是让 x 到 rootY 的权值和 y 到 rootY 的权值满足给定关系。从 x 出发经过 weight[x] 到 rootX再经过 weight[rootX] 到 rootY总权值应该等于 d 加权值 y 到 rootY 的路径补全。多画几张图就能理解。带权并查集的价值在于你能在维护连通性的同时维护集合内部元素之间的代数关系距离、差值、相对顺序等。我后来处理“银河英雄传说”那道题时需要维护每个战舰到队首的距离用的就是同一个套路只是权值从模 3 关系变成了实际距离累加。5. 手写实现时的常见坑与排查经验5.1 find 的递归写法小心栈溢出路径压缩的递归写法虽然简洁但在极端情况下有栈溢出风险。当树高达到数万甚至数十万时递归深度会超过默认栈限制程序直接崩溃。我在一个百万级节点的并查集上测过如果只按秩合并而不做路径压缩树高上限是 log n 级别的递归没问题。但如果某些地方写错了树退化成链递归深度就是节点数栈不爆才怪。如果你在项目里担心这点用迭代版 find 更安全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; }这个版本没有任何递归性能稳定推荐在工程代码里使用。竞赛里用递归写是因为代码短、看起来优雅但真要长期维护迭代版是更稳妥的选择。5.2 合并方向swap 调用的效果写 unite 时最简单的写法是if (rank_[rootX] rank_[rootY]) { parent[rootX] rootY; } else { parent[rootY] rootX; }相当于默认让 rootX 作为新根除非 rootX 的秩比 rootY 小。但如果换一种思路先做 swap 再统一处理代码会更清晰if (rank_[rootX] rank_[rootY]) swap(rootX, rootY); parent[rootY] rootX; if (rank_[rootX] rank_[rootY]) rank_[rootX];swap 之后rootX 一定是秩较大的那一个后续逻辑统一处理即可不容易漏分支。两段代码等价但 swap 版本我私心推荐因为少了 else 分支嵌套降低了写错的可能。5.3 初始化顺序与“孤岛”问题并查集最常见的隐性 bug 就是初始化遗漏。比如你只初始化了部分节点后面的节点 parent[i] 是垃圾值find 会指向任意内存导致查询结果完全随机。另一个容易忽略的问题是“孤立节点”。如果你的数据中有节点自始至终没有参与任何合并它的 parent 始终等于自己find 返回它自己这是正确的。但如果你在写代码时假设“所有节点最终都合并到同一个集合”那统计结果就会出问题。所以写并查集时我习惯在构造完对象后立刻把所有 parent[i] 初始化好并且写一个测试用例专门验证“没有合并过的节点表现正常”。5.4 带权并查集的方向约定我踩过的坑带权并查集最难的不是 find 的更新而是合并时的方向约定。我踩过的坑是合并两个集合时把 rootX 和 rootY 的顺序搞反导致所有后续关系全部偏置。调试这类问题最有效的方法是小规模数据逐步模拟构造 3-4 个节点手动合并几次每一步都打印出每个节点的 parent 和 weight看看数据的相对关系是否符合预期。不要在大数据上瞎试那只会浪费时间。还有一个经验是给 weight 数组初始化为 0 一定要做因为 0 通常表示“与自身同类”的默认关系。如果忘记初始化后续取模运算得到的结果毫无意义。6. 进阶变体可撤销并查集与维护额外信息6.1 可撤销并查集支持回滚的版本普通并查集不支持“撤销最后一次合并”。但在一些搜索算法和离线问题里你需要在 DFS 回溯时恢复到之前的状态这时候就需要可撤销并查集。实现思路并不复杂因为每次合并实际上只修改了两个数组元素parent 和 rank只要把修改前的值记录到一个栈里回滚时弹栈还原即可。但这里有一个关键要求可撤销并查集不能用路径压缩。原因很直接路径压缩会修改路径上很多节点的 parent 指针万一要回滚栈里得存一整个路径的信息复杂度就失控了。所以可撤销版本只保留按秩合并这样单次合并只改了常数个位置回滚成本是 O(1)。struct Change { int pos; int oldVal; }; vectorChange history; void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { history.push_back({-1, -1}); // 空操作标记 return; } if (rank_[rootX] rank_[rootY]) swap(rootX, rootY); history.push_back({rootY, parent[rootY]}); parent[rootY] rootX; if (rank_[rootX] rank_[rootY]) { history.push_back({rootX, rank_[rootX]}); rank_[rootX]; } } void rollback() { Change c history.back(); history.pop_back(); if (c.pos ! -1) parent[c.pos] c.oldVal; if (!history.empty()) { c history.back(); history.pop_back(); if (c.pos ! -1) rank_[c.pos] c.oldVal; } }这个变体在“动态图问题”里特别有用比如判断一个图是否是二分图的某个动态版本处理到一半要回退用可撤销并查集就能高效维护。6.2 维护集合大小与附加信息有时候不仅要知道两个元素是否同集合还要知道某个集合里有多少元素。按大小合并天然支持这个size_[rootX] size_[rootY];除了大小你还可以在根节点上维护任何你关心的集合级信息比如集合的总和、最大最小值。合并时只需要把两个根的信息合并sum[rootX] sum[rootY]; maxVal[rootX] max(maxVal[rootX], maxVal[rootY]);这相当于把并查集变成了一个简易的“集合信息维护器”。我在处理一些图聚类时会用并查集维护聚类大小和中心点坐标的累加和最后统一算平均值逻辑非常简单。6.3 什么时候不该用并查集讲到这里我想多分享一些我自己的体会。并查集虽然强大但它的能力边界也很明确。需要动态删边时如果问题在线不能预知后续操作并查集做不了得上 LCTLink-Cut Tree这类更重的结构。需要输出具体连通路径时并查集只告诉你“通不通”不告诉你“怎么通”此时维护图结构或做搜索才是正确的。需要维护集合内部顺序关系时并查集只适用于等价关系自反、对称、传递如果你要维护的是偏序关系它无能为力。需要合并的规模不平衡时比如每次合并前要检查大量不同集合之间的条件关系并查集虽然能快速合并但你仍然需要其他数据结构辅助枚举和筛选。所以在实际工程和刷题中我习惯先问三个问题操作是合并还是删除查询是判连通还是求路径数据范围允不允许离线这些问题想清楚再动手写代码基本不会走弯路。并查集最让我欣赏的一点是它把“群体归属”这种看似抽象的概念变成了几个指针操作。几十行代码复杂度接近常数却能在百万甚至千万级的动态场景下稳定工作。有时候复杂的业务问题抽丝剥茧后底层就是一个并查集——这也是我为什么一直建议每个做算法和做工程的开发者都花心思把这个结构吃透的原因。