并查集这名字听起来像个数学概念实际上却是图论与算法竞赛里最像工具的一种数据结构。很多人第一次接触它是在做无向图连通块统计、判断两个点是否连通、或者写Kruskal最小生成树的时候——它几乎是一类问题的标准答案。简单说并查集擅长维护若干个不相交的元素集合支持快速地合并两个集合以及查询两个元素是否属于同一个集合。如果你在做图论相关开发、刷算法题或者准备面试这套东西值得彻底搞明白因为它的代码量很少思想却非常精巧。这篇文章我会从最基础的问题出发把并查集从为什么需要讲到怎么写正确再深入到路径压缩、按秩合并、带权并查集这些进阶玩法最后总结我实际写代码踩过的坑。全程会用具体的例子和完整代码讲解不绕弯子。1. 核心问题与整体设计思路1.1 它到底解决什么问题先想一个最简单的场景一个社交平台上有N个用户后台日志记录了M和N成为了好友。好友关系是可以传递的——如果A和B是好友B和C是好友那么A和C在逻辑上就是二度好友三个人应该被划分进同一个社交圈。现在运营人员想知道任意两个人是否属于同一个社交圈或者想统计当前的社交圈有多少个。用图论的视角看用户是结点好友关系是边。问题就变成了在一个动态加边的无向图中随时回答两个点目前连通吗。如果每次提问都从头跑一遍DFS或BFS当图很大、询问频繁时代价是灾难性的。因为图的边数可能达到几十万甚至上千万而查询也可能有几十万次。并查集就是为这种动态连通性问题量身定做的。它不是去遍历整个图而是给每个集合选出代表让每个元素只要能报告我的代表是谁就能在近O(1)时间内完成连通性判断。1.2 核心思想用一个父指针森林表达归属关系并查集的底层结构非常朴素甚至朴素到初学者会觉得不可思议——它就是一个数组。假设我们有N个元素编号从0或1开始数组里每个位置存的是我的父节点是谁初始时每个元素都是自己的父节点也就是每个元素独自构成一个集合集合的代表就是它自己。当我们要把两个元素所在的集合合并时做法不是真的把集合里所有元素都搬运到一起而是只动两个代表的关系找到元素x所在集合的代表找到元素y所在集合的代表然后把其中一个代表的父指针指向另一个代表。这个操作的时间开销与集合大小无关只取决于找代表的速度。这里的关键在于找代表这个操作。因为每个元素都有一条向上走的链——父节点再找父节点的父节点直到某个节点的父节点是它自己这个节点就是整个集合的代表。这个过程我们一般叫它find函数。合并的过程叫做union先各自找到根再挂接。用生活化的类比来理解某个村子里每个家族都有一个族长普通人想确认自己是不是和另一个人同族只需要顺着长辈的链条往上追溯看看最终是不是落到同一个族长的名下。合族的时候更是省事只需要让两个族长达成一致让其中一个族长宣告以后大家都听我的两族的人就自动成一家了。这就是并查集效率高的根本原因——信息全部记录在代表这个单一关键节点上其他人不需要挨个通知。2. 基础实现与两个关键优化2.1 朴素并查集的实现与局限先给出最原始的版本用C写结构一目了然#include vector using namespace std; class DSU { public: vectorint parent; // 初始化n个元素parent[i] i DSU(int n) : parent(n 1) { for (int i 0; i n; i) { parent[i] i; } } // 查找根递归一直往上走 // 当 parent[x] x说明x就是当前集合的代表 int find(int x) { if (parent[x] x) return x; return find(parent[x]); } // 合并把x所在集合和y所在集合合并 void unite(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return; // 已经在同一个集合里了 parent[rx] ry; // 让rx的父节点指向ry } // 查询两个元素是否连通 bool same(int x, int y) { return find(x) find(y); } };这个版本的功能是完整正确的但性能隐患很大。假设我们不停地执行这样的合并操作把集合1合并到集合2再把集合1合并到集合3再把集合1合并到集合4……由于我们每次都让较小的根挂到较深的根下面树会越长越高。最坏情况下整棵树会拉成一条链此时find(最底层节点)要走N步一次查询O(N)m次操作就是O(N*m)数据稍大一点直接超时。2.2 路径压缩让树变扁我实际写代码时几乎从不会写上面那个朴素版本第一件事就是加路径压缩。路径压缩的思想特别直白一个节点找到根之后就直接把它的父指针指向根。这样下次再查同一个节点一步就能到根了。更聪明的做法是让查找路径上的所有节点都这么做。递归实现极其简单int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; }这行代码只在原有递归版find上多了一个赋值。它产生的实际效果是每次find都会压扁整条查询路径让沿途所有节点直接挂到根下面。做过几次find之后树的高度会变得非常低。路径压缩的极致场景是这样的一个深度为十亿的链假设内存允许第一次find最底部的节点会递归十亿层但返回时十亿个节点全部直接指向根了。从此以后这十亿个节点的任何查询都是O(1)的。这就是为什么并查集实践里看起来几乎常数的原因——单个操作的均摊代价极其低。提示路径压缩最标准的写法就是在递归返回时把父指针直接赋值为根。如果你担心递归层数过深导致栈溢出可以改成循环实现后面4.1节会给出。2.3 按秩合并或按大小合并防止树退化成链只有路径压缩其实已经能应付绝大多数情况但如果数据允许构造性退化成链再查询先串成一棵大链再进行第一次查询那这次查询的代价仍然是O(N)的。为了进一步保证树的平衡我们引入按秩/按大小合并。所谓秩可以简单理解为树的高度。按秩合并的意思是合并时总是把高度较小的树挂到高度较大的树下面。这样不会增加大树的高度只有两棵树高度相同时才可能让新高度加1。另一种等价写法是按大小合并即比较的是子树里节点的数量。节点少的树挂到节点多的树下面。这样做的好处是直观、容易理解而且在维护集合大小的场景下代码更紧凑。代码里需要额外维护一个rank或size数组class DSU { public: vectorint parent, sz; DSU(int n) : parent(n 1), sz(n 1, 1) { 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 rx find(x); int ry find(y); if (rx ry) return; // 按大小合并小树挂大树下面 if (sz[rx] sz[ry]) swap(rx, ry); parent[ry] rx; sz[rx] sz[ry]; } bool same(int x, int y) { return find(x) find(y); } };同时用路径压缩和按大小合并单个操作的均摊复杂度是O(α(n))α是反阿克曼函数。反阿克曼函数增长慢到离谱对于任何现实中能见到的n它的值都不超过4或5。这意味着实际使用中并查集可以看作常数时间操作。2.4 为什么初始化时parent[i] i是最优约定刚开始接触并查集的人经常问为什么每个节点的父亲是自己而不是置为-1或者其他什么值这里的关键在于find的终止条件是父节点等于自己。用自己作根天然携带了我是代表的信息不需要额外判断我这节点的父亲是不是非法的。存储上还节省了另一个标记数组。如果用-1表示根节点find里要对每个节点判断这里是不是-1逻辑上没有任何问题但合并时你需要维护的信息变成了我是负数代表根绝对值代表集合大小代码会绕很多。工程实践上self-root约定最干净而且它不需要额外边界处理。C、Python、Java各语言版本我都试过自指写法最不容易出错。3. 实操过程与经典应用场景3.1 场景一统计无向图连通块数量这是我个人觉得最舒服的入门练习题。给定一张N个点、M条边的无向图求连通块数量。做法很简单先建一个N个点的并查集然后依次读入每条边的两个端点调用unite合并。合并完成后遍历所有点统计有多少个点的parent[x] x这个数字就是连通块数量。这里有个容易被忽略的细节统计时必须用find(x)不能直接比较parent[x] x。因为路径压缩是懒的可能有某些节点的父亲仍然指向旧根旧根又指向新根。如果你直接相信parent数组可能统计出多余的块数。我在初学阶段就被这个问题坑过。一个常见变体是动态加边动态查询连通性比如网络中有若干台路由器每新接入一条连线就要更新整个网络的分块数量。直接累加统计不现实可以用一个变量cnt保存连通块数量。初始cnt N每一次合并操作中如果rx和ry不同合并后cnt--如果相同cnt不变。这样每次操作后cnt就是实时的连通块数无需遍历全图。3.2 场景二Kruskal最小生成树与并查集的关系图论里最经典的并查集应用是Kruskal算法求最小生成树。算法的执行过程是把所有边按权重从小到大排序然后依次尝试把每条边的两端加入同一个集合如果这轮尝试时两端原本不在同一个集合意味着加入这条边不会形成环就选中这条边并合并两端如果两端已经在同一个集合里说明加上这条边会形成环直接跳过。选举过程背后的逻辑就是判断这条边连接的两个节点是否已连通。这个判断如果不用并查集每加一条边就去图里跑一趟搜索整个复杂度就是O(M*(NM))用了并查集总复杂度只有排序的O(M log M)加M次近似O(1)的混合操作。实现时注意一点Kruskal需要记录每条边是否被选中单纯判断连通是不够的。但核心的成环检测就是并查集的same函数代码上你只需要在unite前检查一下rx ! ry即可。3.3 场景三带权并查集——不只是连通关系有时候题目问的不只是两个点连不连而是两个点之间的关系是什么关系。最典型的例子是食物链模型三类物种之间存在捕食关系描述为x吃y或x和y同类要求维护所有关系并实时回答矛盾查询。这种时候单纯合并节点显然不够需要在find或unite过程中维护节点到根的关系权值。带权并查集的思路是为每个节点维护一个val[i]表示节点i和它的父节点之间的某种差值或关系。在find路径压缩时因为父节点可能在压缩过程中被直接挂到根上所以val也要同步更新为节点i到根节点的关系。合并时则需要根据两端各自到根的关系反推出两个根之间应该建立什么关系。以最简的模三食物链为例假设val[i]表示i被它的父节点吃的话为1i吃父节点为2同类为0。递归路径压缩时int find(int x) { if (parent[x] ! x) { int orig_parent parent[x]; parent[x] find(parent[x]); val[x] (val[x] val[orig_parent]) % 3; } return parent[x]; }注意一定要先保存原父节点再递归find否则父节点变化后val累加会出错。合并规则也像做向量加法一样推。我第一次看到这个写法时觉得像是玄学但实际推演一遍就通了带权并查集本质上是在森林上维护节点到根的距离向量所有关系都在根处归结。带权并查集常见应用还包括区间求和问题里的并查集维护前缀和偏移量、奇偶性判定问题里的模二关系边权等。它扩展了并查集的语义边界也提升了面试题的区分度。3.4 场景四离线处理与启发式合并——并查集的反操作问题并查集只支持合并不支持删除边这是它的一个天然局限。实际应用里如果题目是删边查询连通性直接维护并查集很痛苦。常见套路是离线逆向处理既然正着走要删边那就把所有操作存下来把最终状态变成初始状态从最后一个操作开始反着处理——原来的删边操作在倒推时变成了加边。这一步做完所有查询都在并查集上正着进行即可。这个方法在竞赛题里出现频率非常高。它本质上是利用了并查集只能加边不能删边的特点用时间倒流来规避删边操作。注意实现上先把所有后续会被删掉的边预处理出来初始并查集里只包含最终保留的边然后按操作逆序处理每个查询或删边/加边。还有另一个与之相关的扩展叫可撤销并查集或支持回滚的并查集做法是记录每次合并的修改点用栈存储操作历史回退时逆操作恢复。这种写法要求不能使用路径压缩不然压平了回滚不了只能靠按秩合并来保证log级别的复杂度。大家如果做题时遇到离线区间询问连通性往往就是这类技巧的舞台。4. 常见问题与排查技巧实录4.1 递归find爆栈问题路径压缩的递归写法虽然简洁但在极深的树上会爆栈。尤其是某些输入数据会故意构造深度很大的场景或者图论题里节点数达到几十万甚至上百万。此时我把find改成循环版本先用迭代找到根再走一遍路径把所有节点挂到根下面int find(int x) { int root x; while (parent[root] ! root) root parent[root]; // 第二遍循环路径压缩 while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }第一次循环找到根第二次循环把路径上每个节点直接指向根。代价是两次遍历路径但均摊复杂度仍然接近常数而且彻底避免递归开销。我个人推荐在比赛和实际工程环境里除非题目的数据规模很小否则都用这版循环find。4.2 合并后忘记更新根的信息这是新手最容易犯的错。如果你用按大小合并那种写法朴素代码里很容易只修改parent[ry] rx却忘记更新sz[rx] sz[ry]。表面上看合并操作还能工作——因为find对sz数组并不敏感只有统计集合大小的时候才暴露问题。统计结果一会儿对一会儿错排查起来相当难受。解决思路很简单把维护sz或rank和合并逻辑写成一个专门的函数或者养成习惯写完unite立刻检查所有辅助数组是否同步更新。我个人的习惯是定义并查集类时把find和unite放在一起并且在unite里用注释标注这里必须维护sz更新。4.3 并查集的类型不匹配问题节点编号从0还是从1开始很多题面里元素编号从1开始比如输入N个点1到N的编号。这时候如果你初始化成0到N后续访问parent[N]会越界如果你初始化成0到N-1读入编号1的节点时就会出错。最省心的做法是读题后立刻确认编号范围初始化时统一用size n1从下标0建到下标n。这样不管输入是0还是1开头下标0是闲置的所有节点都是安全的。4.4 查询是否连通时误用parent数组我在3.1里强调过一次但这里值得再猛敲一遍永远不要直接用parent[x] parent[y]判断连通性必须调用find。原因是路径压缩是懒压缩父指针并不可靠。举个例子x和y在同一个集合里但x的父指针还指向旧根y已经指向新根此时parent[x] ! parent[y]直接比较就会判断成不连通。这个bug隐蔽性极高因为大部分情况下数据碰巧让父指针相等偶尔出错又偶发通过最折磨人。测试建议准备一个集合反复做多次合并和查询并穿插查询随机点对确认所有same(x, y)结果与预期一致再提交代码。4.5 并查集的性能定位与Ac用时排查如果题目超时了怎么判断是不是并查集写法有问题先想一种情况你已经用了递归find和按大小合并理论复杂度是很好的但实际实现了爆栈。另一种情况是每次操作都调用两次find而每次find内部又有一层循环整体串起来多出常数开销。如果数据量特别大百万级这些常数会让时间翻倍。排查技巧先本机造极限数据看递归版是否抛出栈溢出错误再用循环版对比运行时间。如果循环版也慢检查是不是频繁调用same函数后再调用unite导致每个操作调用多次find——你可以在unite函数内部把rx和ry直接找出来在same场景下直接返回避免重复find。注意路径压缩和按秩/大小合并一旦同时使用find内部其实已经包含了压缩此时如果你在unite里面为了拿rx和ry又额外调用了两次find那一次合并就会发生多次压缩但没有实际性能收益。优化做法是unite直接接收调用者已经算好的rx和ry或者干脆让调用的地方手动先find。4.6 典型题目难度定位速查表题目特征所需技巧难度判断两个点是否连通、统计连通块基础find/unite入门最小生成树的成环判定Kruskal 并查集基础判断图是否有环/成环路径计数合并时发现rxry即构成环基础维护集合大小按大小合并 sz数组同步更新入门进阶食物链/种类关系约束带权并查集模域关系进阶奇偶关系判断区间前缀异或带权并查集维护偏移量进阶删边查询连通性离线倒推进阶支持回滚的并查集按秩合并栈记录历史较难动态维护最小生成树边的取舍并查集与边排序配合较难5. 进阶技巧与练习建议5.1 扩展域并查集把关系归类变成关系分身带权并查集可以处理关系型约束还有一种更直观的写法叫扩展域或种类并查集。思路是把每个节点拆成多个分身分别表示本体的不同身份状态。比如只有三种动物X吃Y、Y吃Z、Z吃X这样的题目可以把每个动物i拆成三个节点i表示i是A类in表示i是B类i2n表示i是C类。用并查集把同类捕食关系转化为分身之间属于同一集合的关系。这种方法的原因论很简单它不维护边权而是直接扩展节点维度用分身的连通性来编码关系。实际写起来甚至比带权并查集更容易理解缺点是需要开3倍甚至k倍的空间。有些题目的条件类型很多k种扩展域写法非常直观劣势是空间消耗线性增长但一般题目能接受。5.2 并查集的实践工程细节在实际项目代码里并查集常常作为图算法的底层组件。比如处理社交网络的好友推荐、检测网络中的环路、判断数据库外键的依赖是否成环等场景。工程代码建议封装成类不要散落成全局数组。find和unite都做成公开接口same合并为unite的返回值。如果多次重复构建可以考虑复用vector内存避免频繁new/delete。多线程环境下并查集不是线程安全的需要加锁或者做本地副本不过绝大多数场景是单线程的多阶段图算法不必过度设计。5.3 练习建议从入门到融会贯通如果自学者想系统性练起来我给的练习路径是这样先找三道纯模板题把find、unite、same熟练到能盲写再做一道连通块计数一道Kruskal生成树然后进入带权并查集至少做两道模关系题把val的更新推到自己能独立推导的程度最后尝试一题离线倒推删边和一题可撤销回滚的题把时间倒流和栈回滚这两个高级技巧也吃透。完成这条路线后常见图论题里见到并查集三个字基本不需要再看题解就能设计出方案。6. 我个人在实际写码中的几点体会回头来看并查集是复杂度与代码量之间平衡得最好的数据结构之一。完整的union-find核心代码不超过20行却能把最坏O(N*m)的动态连通性判断压缩到几乎O(m)。这种用思想换速度的设计是值得反复品味的。再说一个实操中发现的小技巧如果不需要统计集合大小在只做连通性判断的场景里按大小合并其实不比按秩合并差而且sz数组还能顺便提供集合大小遇到每次合并后需要知道新集合多大的需求时直接读sz[根]就行。这也是我推荐按大小合并多于按秩合并的原因——反正时间复杂度同一级别多一个有用信息总是好的。还有一个小经验是无论用什么语言并查集的测试都建议随机生成操作序列与暴力DFS对拍。因为这类问题的反直觉bug很容易藏在看起来正确的合并逻辑里。我个人的习惯是写一个O(NM)的暴力连通性检查作为基准随机跑几百组小数据和并查集答案比对。几次对拍下来代码的正确性基本就有保障了。希望这篇把并查集从设计原理到工程落地聊透彻的文章能帮你彻底告别看起来会了、一写就错的状态。拿着模板去练几道题这20行代码会成为你图论工具箱里最顺手的那个工具。 
长河君 · 2026/10/13 16:41:20 · 阅读 1.2k 并查集详解：从路径压缩到带权并查集，一文打通图论连通性
并查集这名字听起来像个数学概念实际上却是图论与算法竞赛里最像工具的一种数据结构。很多人第一次接触它是在做无向图连通块统计、判断两个点是否连通、或者写Kruskal最小生成树的时候——它几乎是一类问题的标准答案。简单说并查集擅长维护若干个不相交的元素集合支持快速地合并两个集合以及查询两个元素是否属于同一个集合。如果你在做图论相关开发、刷算法题或者准备面试这套东西值得彻底搞明白因为它的代码量很少思想却非常精巧。这篇文章我会从最基础的问题出发把并查集从为什么需要讲到怎么写正确再深入到路径压缩、按秩合并、带权并查集这些进阶玩法最后总结我实际写代码踩过的坑。全程会用具体的例子和完整代码讲解不绕弯子。1. 核心问题与整体设计思路1.1 它到底解决什么问题先想一个最简单的场景一个社交平台上有N个用户后台日志记录了M和N成为了好友。好友关系是可以传递的——如果A和B是好友B和C是好友那么A和C在逻辑上就是二度好友三个人应该被划分进同一个社交圈。现在运营人员想知道任意两个人是否属于同一个社交圈或者想统计当前的社交圈有多少个。用图论的视角看用户是结点好友关系是边。问题就变成了在一个动态加边的无向图中随时回答两个点目前连通吗。如果每次提问都从头跑一遍DFS或BFS当图很大、询问频繁时代价是灾难性的。因为图的边数可能达到几十万甚至上千万而查询也可能有几十万次。并查集就是为这种动态连通性问题量身定做的。它不是去遍历整个图而是给每个集合选出代表让每个元素只要能报告我的代表是谁就能在近O(1)时间内完成连通性判断。1.2 核心思想用一个父指针森林表达归属关系并查集的底层结构非常朴素甚至朴素到初学者会觉得不可思议——它就是一个数组。假设我们有N个元素编号从0或1开始数组里每个位置存的是我的父节点是谁初始时每个元素都是自己的父节点也就是每个元素独自构成一个集合集合的代表就是它自己。当我们要把两个元素所在的集合合并时做法不是真的把集合里所有元素都搬运到一起而是只动两个代表的关系找到元素x所在集合的代表找到元素y所在集合的代表然后把其中一个代表的父指针指向另一个代表。这个操作的时间开销与集合大小无关只取决于找代表的速度。这里的关键在于找代表这个操作。因为每个元素都有一条向上走的链——父节点再找父节点的父节点直到某个节点的父节点是它自己这个节点就是整个集合的代表。这个过程我们一般叫它find函数。合并的过程叫做union先各自找到根再挂接。用生活化的类比来理解某个村子里每个家族都有一个族长普通人想确认自己是不是和另一个人同族只需要顺着长辈的链条往上追溯看看最终是不是落到同一个族长的名下。合族的时候更是省事只需要让两个族长达成一致让其中一个族长宣告以后大家都听我的两族的人就自动成一家了。这就是并查集效率高的根本原因——信息全部记录在代表这个单一关键节点上其他人不需要挨个通知。2. 基础实现与两个关键优化2.1 朴素并查集的实现与局限先给出最原始的版本用C写结构一目了然#include vector using namespace std; class DSU { public: vectorint parent; // 初始化n个元素parent[i] i DSU(int n) : parent(n 1) { for (int i 0; i n; i) { parent[i] i; } } // 查找根递归一直往上走 // 当 parent[x] x说明x就是当前集合的代表 int find(int x) { if (parent[x] x) return x; return find(parent[x]); } // 合并把x所在集合和y所在集合合并 void unite(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return; // 已经在同一个集合里了 parent[rx] ry; // 让rx的父节点指向ry } // 查询两个元素是否连通 bool same(int x, int y) { return find(x) find(y); } };这个版本的功能是完整正确的但性能隐患很大。假设我们不停地执行这样的合并操作把集合1合并到集合2再把集合1合并到集合3再把集合1合并到集合4……由于我们每次都让较小的根挂到较深的根下面树会越长越高。最坏情况下整棵树会拉成一条链此时find(最底层节点)要走N步一次查询O(N)m次操作就是O(N*m)数据稍大一点直接超时。2.2 路径压缩让树变扁我实际写代码时几乎从不会写上面那个朴素版本第一件事就是加路径压缩。路径压缩的思想特别直白一个节点找到根之后就直接把它的父指针指向根。这样下次再查同一个节点一步就能到根了。更聪明的做法是让查找路径上的所有节点都这么做。递归实现极其简单int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; }这行代码只在原有递归版find上多了一个赋值。它产生的实际效果是每次find都会压扁整条查询路径让沿途所有节点直接挂到根下面。做过几次find之后树的高度会变得非常低。路径压缩的极致场景是这样的一个深度为十亿的链假设内存允许第一次find最底部的节点会递归十亿层但返回时十亿个节点全部直接指向根了。从此以后这十亿个节点的任何查询都是O(1)的。这就是为什么并查集实践里看起来几乎常数的原因——单个操作的均摊代价极其低。提示路径压缩最标准的写法就是在递归返回时把父指针直接赋值为根。如果你担心递归层数过深导致栈溢出可以改成循环实现后面4.1节会给出。2.3 按秩合并或按大小合并防止树退化成链只有路径压缩其实已经能应付绝大多数情况但如果数据允许构造性退化成链再查询先串成一棵大链再进行第一次查询那这次查询的代价仍然是O(N)的。为了进一步保证树的平衡我们引入按秩/按大小合并。所谓秩可以简单理解为树的高度。按秩合并的意思是合并时总是把高度较小的树挂到高度较大的树下面。这样不会增加大树的高度只有两棵树高度相同时才可能让新高度加1。另一种等价写法是按大小合并即比较的是子树里节点的数量。节点少的树挂到节点多的树下面。这样做的好处是直观、容易理解而且在维护集合大小的场景下代码更紧凑。代码里需要额外维护一个rank或size数组class DSU { public: vectorint parent, sz; DSU(int n) : parent(n 1), sz(n 1, 1) { 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 rx find(x); int ry find(y); if (rx ry) return; // 按大小合并小树挂大树下面 if (sz[rx] sz[ry]) swap(rx, ry); parent[ry] rx; sz[rx] sz[ry]; } bool same(int x, int y) { return find(x) find(y); } };同时用路径压缩和按大小合并单个操作的均摊复杂度是O(α(n))α是反阿克曼函数。反阿克曼函数增长慢到离谱对于任何现实中能见到的n它的值都不超过4或5。这意味着实际使用中并查集可以看作常数时间操作。2.4 为什么初始化时parent[i] i是最优约定刚开始接触并查集的人经常问为什么每个节点的父亲是自己而不是置为-1或者其他什么值这里的关键在于find的终止条件是父节点等于自己。用自己作根天然携带了我是代表的信息不需要额外判断我这节点的父亲是不是非法的。存储上还节省了另一个标记数组。如果用-1表示根节点find里要对每个节点判断这里是不是-1逻辑上没有任何问题但合并时你需要维护的信息变成了我是负数代表根绝对值代表集合大小代码会绕很多。工程实践上self-root约定最干净而且它不需要额外边界处理。C、Python、Java各语言版本我都试过自指写法最不容易出错。3. 实操过程与经典应用场景3.1 场景一统计无向图连通块数量这是我个人觉得最舒服的入门练习题。给定一张N个点、M条边的无向图求连通块数量。做法很简单先建一个N个点的并查集然后依次读入每条边的两个端点调用unite合并。合并完成后遍历所有点统计有多少个点的parent[x] x这个数字就是连通块数量。这里有个容易被忽略的细节统计时必须用find(x)不能直接比较parent[x] x。因为路径压缩是懒的可能有某些节点的父亲仍然指向旧根旧根又指向新根。如果你直接相信parent数组可能统计出多余的块数。我在初学阶段就被这个问题坑过。一个常见变体是动态加边动态查询连通性比如网络中有若干台路由器每新接入一条连线就要更新整个网络的分块数量。直接累加统计不现实可以用一个变量cnt保存连通块数量。初始cnt N每一次合并操作中如果rx和ry不同合并后cnt--如果相同cnt不变。这样每次操作后cnt就是实时的连通块数无需遍历全图。3.2 场景二Kruskal最小生成树与并查集的关系图论里最经典的并查集应用是Kruskal算法求最小生成树。算法的执行过程是把所有边按权重从小到大排序然后依次尝试把每条边的两端加入同一个集合如果这轮尝试时两端原本不在同一个集合意味着加入这条边不会形成环就选中这条边并合并两端如果两端已经在同一个集合里说明加上这条边会形成环直接跳过。选举过程背后的逻辑就是判断这条边连接的两个节点是否已连通。这个判断如果不用并查集每加一条边就去图里跑一趟搜索整个复杂度就是O(M*(NM))用了并查集总复杂度只有排序的O(M log M)加M次近似O(1)的混合操作。实现时注意一点Kruskal需要记录每条边是否被选中单纯判断连通是不够的。但核心的成环检测就是并查集的same函数代码上你只需要在unite前检查一下rx ! ry即可。3.3 场景三带权并查集——不只是连通关系有时候题目问的不只是两个点连不连而是两个点之间的关系是什么关系。最典型的例子是食物链模型三类物种之间存在捕食关系描述为x吃y或x和y同类要求维护所有关系并实时回答矛盾查询。这种时候单纯合并节点显然不够需要在find或unite过程中维护节点到根的关系权值。带权并查集的思路是为每个节点维护一个val[i]表示节点i和它的父节点之间的某种差值或关系。在find路径压缩时因为父节点可能在压缩过程中被直接挂到根上所以val也要同步更新为节点i到根节点的关系。合并时则需要根据两端各自到根的关系反推出两个根之间应该建立什么关系。以最简的模三食物链为例假设val[i]表示i被它的父节点吃的话为1i吃父节点为2同类为0。递归路径压缩时int find(int x) { if (parent[x] ! x) { int orig_parent parent[x]; parent[x] find(parent[x]); val[x] (val[x] val[orig_parent]) % 3; } return parent[x]; }注意一定要先保存原父节点再递归find否则父节点变化后val累加会出错。合并规则也像做向量加法一样推。我第一次看到这个写法时觉得像是玄学但实际推演一遍就通了带权并查集本质上是在森林上维护节点到根的距离向量所有关系都在根处归结。带权并查集常见应用还包括区间求和问题里的并查集维护前缀和偏移量、奇偶性判定问题里的模二关系边权等。它扩展了并查集的语义边界也提升了面试题的区分度。3.4 场景四离线处理与启发式合并——并查集的反操作问题并查集只支持合并不支持删除边这是它的一个天然局限。实际应用里如果题目是删边查询连通性直接维护并查集很痛苦。常见套路是离线逆向处理既然正着走要删边那就把所有操作存下来把最终状态变成初始状态从最后一个操作开始反着处理——原来的删边操作在倒推时变成了加边。这一步做完所有查询都在并查集上正着进行即可。这个方法在竞赛题里出现频率非常高。它本质上是利用了并查集只能加边不能删边的特点用时间倒流来规避删边操作。注意实现上先把所有后续会被删掉的边预处理出来初始并查集里只包含最终保留的边然后按操作逆序处理每个查询或删边/加边。还有另一个与之相关的扩展叫可撤销并查集或支持回滚的并查集做法是记录每次合并的修改点用栈存储操作历史回退时逆操作恢复。这种写法要求不能使用路径压缩不然压平了回滚不了只能靠按秩合并来保证log级别的复杂度。大家如果做题时遇到离线区间询问连通性往往就是这类技巧的舞台。4. 常见问题与排查技巧实录4.1 递归find爆栈问题路径压缩的递归写法虽然简洁但在极深的树上会爆栈。尤其是某些输入数据会故意构造深度很大的场景或者图论题里节点数达到几十万甚至上百万。此时我把find改成循环版本先用迭代找到根再走一遍路径把所有节点挂到根下面int find(int x) { int root x; while (parent[root] ! root) root parent[root]; // 第二遍循环路径压缩 while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }第一次循环找到根第二次循环把路径上每个节点直接指向根。代价是两次遍历路径但均摊复杂度仍然接近常数而且彻底避免递归开销。我个人推荐在比赛和实际工程环境里除非题目的数据规模很小否则都用这版循环find。4.2 合并后忘记更新根的信息这是新手最容易犯的错。如果你用按大小合并那种写法朴素代码里很容易只修改parent[ry] rx却忘记更新sz[rx] sz[ry]。表面上看合并操作还能工作——因为find对sz数组并不敏感只有统计集合大小的时候才暴露问题。统计结果一会儿对一会儿错排查起来相当难受。解决思路很简单把维护sz或rank和合并逻辑写成一个专门的函数或者养成习惯写完unite立刻检查所有辅助数组是否同步更新。我个人的习惯是定义并查集类时把find和unite放在一起并且在unite里用注释标注这里必须维护sz更新。4.3 并查集的类型不匹配问题节点编号从0还是从1开始很多题面里元素编号从1开始比如输入N个点1到N的编号。这时候如果你初始化成0到N后续访问parent[N]会越界如果你初始化成0到N-1读入编号1的节点时就会出错。最省心的做法是读题后立刻确认编号范围初始化时统一用size n1从下标0建到下标n。这样不管输入是0还是1开头下标0是闲置的所有节点都是安全的。4.4 查询是否连通时误用parent数组我在3.1里强调过一次但这里值得再猛敲一遍永远不要直接用parent[x] parent[y]判断连通性必须调用find。原因是路径压缩是懒压缩父指针并不可靠。举个例子x和y在同一个集合里但x的父指针还指向旧根y已经指向新根此时parent[x] ! parent[y]直接比较就会判断成不连通。这个bug隐蔽性极高因为大部分情况下数据碰巧让父指针相等偶尔出错又偶发通过最折磨人。测试建议准备一个集合反复做多次合并和查询并穿插查询随机点对确认所有same(x, y)结果与预期一致再提交代码。4.5 并查集的性能定位与Ac用时排查如果题目超时了怎么判断是不是并查集写法有问题先想一种情况你已经用了递归find和按大小合并理论复杂度是很好的但实际实现了爆栈。另一种情况是每次操作都调用两次find而每次find内部又有一层循环整体串起来多出常数开销。如果数据量特别大百万级这些常数会让时间翻倍。排查技巧先本机造极限数据看递归版是否抛出栈溢出错误再用循环版对比运行时间。如果循环版也慢检查是不是频繁调用same函数后再调用unite导致每个操作调用多次find——你可以在unite函数内部把rx和ry直接找出来在same场景下直接返回避免重复find。注意路径压缩和按秩/大小合并一旦同时使用find内部其实已经包含了压缩此时如果你在unite里面为了拿rx和ry又额外调用了两次find那一次合并就会发生多次压缩但没有实际性能收益。优化做法是unite直接接收调用者已经算好的rx和ry或者干脆让调用的地方手动先find。4.6 典型题目难度定位速查表题目特征所需技巧难度判断两个点是否连通、统计连通块基础find/unite入门最小生成树的成环判定Kruskal 并查集基础判断图是否有环/成环路径计数合并时发现rxry即构成环基础维护集合大小按大小合并 sz数组同步更新入门进阶食物链/种类关系约束带权并查集模域关系进阶奇偶关系判断区间前缀异或带权并查集维护偏移量进阶删边查询连通性离线倒推进阶支持回滚的并查集按秩合并栈记录历史较难动态维护最小生成树边的取舍并查集与边排序配合较难5. 进阶技巧与练习建议5.1 扩展域并查集把关系归类变成关系分身带权并查集可以处理关系型约束还有一种更直观的写法叫扩展域或种类并查集。思路是把每个节点拆成多个分身分别表示本体的不同身份状态。比如只有三种动物X吃Y、Y吃Z、Z吃X这样的题目可以把每个动物i拆成三个节点i表示i是A类in表示i是B类i2n表示i是C类。用并查集把同类捕食关系转化为分身之间属于同一集合的关系。这种方法的原因论很简单它不维护边权而是直接扩展节点维度用分身的连通性来编码关系。实际写起来甚至比带权并查集更容易理解缺点是需要开3倍甚至k倍的空间。有些题目的条件类型很多k种扩展域写法非常直观劣势是空间消耗线性增长但一般题目能接受。5.2 并查集的实践工程细节在实际项目代码里并查集常常作为图算法的底层组件。比如处理社交网络的好友推荐、检测网络中的环路、判断数据库外键的依赖是否成环等场景。工程代码建议封装成类不要散落成全局数组。find和unite都做成公开接口same合并为unite的返回值。如果多次重复构建可以考虑复用vector内存避免频繁new/delete。多线程环境下并查集不是线程安全的需要加锁或者做本地副本不过绝大多数场景是单线程的多阶段图算法不必过度设计。5.3 练习建议从入门到融会贯通如果自学者想系统性练起来我给的练习路径是这样先找三道纯模板题把find、unite、same熟练到能盲写再做一道连通块计数一道Kruskal生成树然后进入带权并查集至少做两道模关系题把val的更新推到自己能独立推导的程度最后尝试一题离线倒推删边和一题可撤销回滚的题把时间倒流和栈回滚这两个高级技巧也吃透。完成这条路线后常见图论题里见到并查集三个字基本不需要再看题解就能设计出方案。6. 我个人在实际写码中的几点体会回头来看并查集是复杂度与代码量之间平衡得最好的数据结构之一。完整的union-find核心代码不超过20行却能把最坏O(N*m)的动态连通性判断压缩到几乎O(m)。这种用思想换速度的设计是值得反复品味的。再说一个实操中发现的小技巧如果不需要统计集合大小在只做连通性判断的场景里按大小合并其实不比按秩合并差而且sz数组还能顺便提供集合大小遇到每次合并后需要知道新集合多大的需求时直接读sz[根]就行。这也是我推荐按大小合并多于按秩合并的原因——反正时间复杂度同一级别多一个有用信息总是好的。还有一个小经验是无论用什么语言并查集的测试都建议随机生成操作序列与暴力DFS对拍。因为这类问题的反直觉bug很容易藏在看起来正确的合并逻辑里。我个人的习惯是写一个O(NM)的暴力连通性检查作为基准随机跑几百组小数据和并查集答案比对。几次对拍下来代码的正确性基本就有保障了。希望这篇把并查集从设计原理到工程落地聊透彻的文章能帮你彻底告别看起来会了、一写就错的状态。拿着模板去练几道题这20行代码会成为你图论工具箱里最顺手的那个工具。