第一次在算法课作业里见到并查集我盯着那二十来行代码看了半天心里嘀咕就这么点东西也能算一个数据结构一个数组、两个函数扫一眼就懂了。结果后来不管是做Kruskal最小生成树、判朋友圈连通性、处理编译原理里的变量等价类还是在面试题和算法竞赛里碰上“给关系和矛盾”的题目绕来绕去最后都会落到并查集身上。它就像一个低调的底层工具代码不炫技但很多看起来复杂的场景一旦想到“用并查集”这个方向解决方案就瞬间清爽了。今天我把并查集从最基础的实现、复杂度分析到带权并查集推导再到实际写代码时容易踩的坑完整拆开讲一遍。期末复习、考研408补基础、刷LeetCode想补强这块的人看完这篇基本够了。1. 并查集到底在解决什么问题1.1 先看一个最典型的应用场景假设你现在做一个社交应用的后台用户之间有“好友关系”你要快速回答“A和B是不是同一个圈子的人”。圈子怎么定义好友的好友也算好友也就是说只要两个人之间存在一条关系链他们就被看成同一个连通团体。这就是典型的连通性问题。换个更经典的场景一张无向图有n个顶点和m条边需要判断两个顶点是否连通。或者反过来一开始所有点互相独立你不断把两个点连起来随时查询两个点的连通状态。这种需求用普通的数据结构并不好办。数组存邻接表查一次连通性要做一次BFS或DFS复杂度跟图的大小直接挂钩。而并查集的思路完全不同它不关心两个点之间是怎么连通的只维护“属于同一个集合”这个事实。所以查询两个点是否连通只需要沿着它们各自的关系链往上一层一层找看看最终找到的“根”是不是同一个。这个抽象方向很重要并查集牺牲了对关系路径的记录换来了动态合并与动态查询的高效。现实中大多数问题也只关心“连不连通”并不需要路径本身因此这种取舍非常划算。1.2 为什么不能用普通的哈希表或集合有人会问既然要维护“集合”我直接用哈希表存多个集合不行吗比如维护一个“集合编号”到成员的映射合并两个集合时把一个集合的所有元素搬到另一个集合里去。思路可行但代价很高。合并操作平均要移动一个集合里一半的元素遇到连续合并n次的场景最坏情况下总复杂度退化成O(n²)。面试题里数据量一旦到十万、百万级别直接超时。并查集反着来它用一棵树来表示一个集合。树的根节点就是集合的代表每个节点只需要记录自己的父节点。合并两个集合时只需要把其中一棵树的根指向另一棵树的根。注意这里没有移动任何成员节点只是改了根的一个指针。查询归属时沿着父指针往上找根即可。整个过程的代价几乎只取决于树的高度而通过路径压缩和按秩合并这个高度可以被压到近乎常数级别。用一句话概括核心思想普通集合关心“里面有什么”并查集只关心“谁是老大”。只要老大相同就认为成员在同一个集合里。1.3 并查集适合的问题类型与个人判断经验我在实际应用中总结出一套判断方法只要题目里出现“若干元素之间满足某种等价关系”“把元素划分为若干互不相交的组”“动态添加关系后查询两个元素是否相关”大概率就能用并查集。几个常见方向图论中的连通分量统计、最小生成树Kruskal算法判环社交网络里的群组划分、共同好友判断数据库或编译原理中的等价类划分比如判断两个变量是否同一类型离线查询中的“时间倒流”问题配合反向删除技巧处理带权扩展后处理“相对关系”类题目比如同类、吃与被吃的关系判断方法有了接下来就进入核心实现环节。2. 核心实现十几行代码如何做到近乎常数时间2.1 最基础的数组实现与两个核心操作并查集的物理存储极其朴素一个一维数组parentparent[i]表示节点i的父节点。初始时每个节点的父节点是自己表示每个元素单独成一个集合自己就是自己的“老大”。两个核心操作分别是find和union。find(x)要做的是不断沿着parent[x]向上跳直到找到根节点也就是满足parent[x] x的那个节点。查找结果就是这个元素所属集合的代表元素。union(x, y)则先分别找到x和y的根节点如果根不同就把其中一个根挂在另一个根下面。这样两个集合合并成一个下次find时双方都会找到同一个根。基础实现代码class DSU { private: vectorint parent; public: DSU(int n) : parent(n) { for (int i 0; i n; i) parent[i] i; } int find(int x) { while (parent[x] ! x) x parent[x]; return x; } void unite(int x, int y) { int rx find(x); int ry find(y); if (rx ! ry) parent[ry] rx; } bool isConnected(int x, int y) { return find(x) find(y); } };这个版本已经能解决连通性问题了但性能不一定稳。问题在于如果合并顺序不理想树会退化成一个长链。比如把0挂在1下面、再把1挂在2下面最后find(0)要一路走到链尾查询复杂度变成O(n)。数据量大时这种退化无法接受。2.2 路径压缩让每个节点直接指向根路径压缩的思路很简单在find的过程中把沿途经过的每个节点都直接挂到根节点下面。这样下次再查询这些节点时一步就能到达根。代码上只需要一行递归int find(int x) { return parent[x] x ? x : parent[x] find(parent[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; }我实测下来递归版本在绝大多数场景都没问题真出现爆栈也几乎都是因为树退化到极致而加上了路径压缩之后这种退化几乎不存在。迭代版的好处是没有任何递归开销适合在嵌入式或极端环境下使用但代码可读性稍差。路径压缩的核心价值在于查询操作不只是“找到老大”它还在顺手优化整棵树的结构。越查越平越查越快。2.3 按秩合并为什么能让树更矮路径压缩解决的是查询路径变长的问题但它有一个盲区如果在很深的树结构上反复调用union每次union都要提前先find这个find会触发路径压缩所以整体还好。不过如果能从一开始就控制树的高度让合并有序进行效果会更好。这就是按秩合并。所谓“秩”通常指树的高度也可以用子树大小。合并两个集合时把高度小的树挂到高度大的树下面。如果两棵树高度相同随便选一棵挂到另一棵下面被挂的那棵树高度加一。实现代码class DSU { private: vectorint parent, rank_; public: DSU(int n) : parent(n), rank_(n, 0) { for (int i 0; i n; i) parent[i] i; } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (rank_[rx] rank_[ry]) swap(rx, ry); parent[ry] rx; if (rank_[rx] rank_[ry]) rank_[rx]; } };路径压缩加按秩合并两个优化一起上并查集的单次操作均摊复杂度是O(α(n))这里的α是反阿克曼函数。这个函数增长慢到什么程度呢n取宇宙中原子数量级别的数字α(n)也超不过5。所以工程上可以放心地认为并查集的单次操作就是常数时间。2.4 复杂度分析里最容易困惑的点很多人背结论“并查集复杂度是O(α(n))”但不知道这个结论成立是有前提的那就是路径压缩和按秩合并必须同时使用。只做路径压缩不做按秩合并或者只按秩合并不压缩路径都能让复杂度退化。前者在极端数据下会退化到O(m log n)后者则退化成O(n)级别的单次查询。另外注意复杂度里的n是节点总数m是操作总数。整个并查集的构建和一系列操作的总复杂度可以写成O(m α(n))但这里“均摊”的意义和普通数据结构里的均摊不太一样。如果不做路径压缩只使用按秩合并单次查询最坏情况下依然是O(log n)也就是说查询仍然和树高相关。只有同时使用路径压缩摊还复杂度才能压到反阿克曼函数级别。这个细节考研408和面试里都很喜欢问。3. 我带一个实战用并查集实现Kruskal最小生成树3.1 Kruskal为什么必须用并查集最小生成树问题目标是在一张带权无向图里选n-1条边把所有点连起来同时保证总边权最小。Kruskal算法的贪心策略是把全部边按权值从小到大排序依次遍历每次尝试把边的两个端点“连起来”但前提是这两个端点之前还没有被连通过。这里就涉及一个高频判断当前边的两个端点是否已经属于同一个连通分量。如果属于加入这条边会形成环必须跳过。如果不属于就加入这条边并合并两个连通分量。这个“判断合并”的需求几乎是为并查集量身定制的。用其他结构做要么代码复杂度高要么时间复杂度高。Kruskal排序部分O(m log m)而并查集部分只需要O(m α(n))整体复杂度由排序主导效率很高。3.2 完整代码与关键步骤推导struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; class DSU { private: vectorint parent, rank_; public: DSU(int n) : parent(n), rank_(n, 0) { for (int i 0; i n; i) parent[i] i; } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } bool unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return false; if (rank_[rx] rank_[ry]) swap(rx, ry); parent[ry] rx; if (rank_[rx] rank_[ry]) rank_[rx]; return true; } }; int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int ans 0, cnt 0; for (const Edge e : edges) { if (dsu.unite(e.u, e.v)) { ans e.w; cnt; if (cnt n - 1) break; } } return cnt n - 1 ? ans : -1; }这里我把unite设计成返回bool成功合并返回true已经在同一集合返回false。这个返回值在Kruskal里非常有用省去额外调用isConnected再unite的两步操作效率更高逻辑也更紧凑。3.3 排序选边时并查集的调用时机这里有个很多人忽略的细节Kruskal必须先把所有边按权值排序。排序之后才进入并查集的循环。为什么不能按输入顺序直接处理因为Kruskal的正确性依赖于贪心选择当前最小权值的边而只有排序后才能保证每次拿到的是当前可选的最小边。回到并查集这边每次遍历到一条边就调用find检查两个端点的根。这里注意一个优化先调用find把两个根的编号记录下来再做合并可以避免unite内部重复find一次。虽然并查集的find很快但竞赛或者面试里这种细节点出来会让代码的档次提升不少。我自己写这个的时候经常犯一个低级错误忘记判断n个点最终是否连成了一棵完整的树也就是cnt是否等于n-1。如果图本身不连通Kruskal不可能生成完整的生成树此时应该返回失败标志。真正写工程代码时这个返回值要明确交给上层处理。一个实用的小技巧如果你在写实验报告经典问题“Kruskal算法为什么要用并查集而不直接用深度优先搜索判断环”答案不是并查集更快而是它天然能维护动态连通分量。DFS每加入一条边都要做一次全图中环的判断单次复杂度O(nm)串起来之后就变成O(m(nm))在稠密图里非常吃亏。4. 进阶带权并查集怎么处理关系冲突4.1 带权并查集的适用模型基础并查集只维护“是否属于同一个集合”信息量有限。但很多实际问题里元素之间的关系不只是“相连”或“不相连”还有相对方向、相对大小、状态差异。比如三国关系里的同类、吃与被吃或者一个班级里两两之间的成绩高低关系。这时就需要带权并查集也就是在并查集的每条边上维护一个权值。每个节点除了存父节点还要存一个到父节点的权值。这个权值不是物理距离而是一种“逻辑偏移量”用来表示当前节点与父节点之间的相对关系。我带的最常见例子是经典的食物链问题三类动物可能处于“同类”“A吃B”“A被B吃”三种关系。题目会给出若干条已知关系有些关系是正确的有些是错误的要求统计错误关系的数量。这里需要把三种关系映射成数字0、1、2再通过模3运算传递关系。映射规则不是唯一的但你一旦定下规则整个推导过程所有公式都要围绕这个规则走。4.2 关系定义与向量偏移法我在代码里习惯这样定义weight[x]表示节点x到其父节点parent[x]的关系取值为0、1、20表示x与父节点是同类1表示x被父节点吃2表示x吃父节点利用模3加减法可以从一个节点一路推到根节点。比如x到根节点r的关系就要把x到parent[x]的关系、parent[x]到grandparent[x]的关系一路累加起来每累加一次对3取模。如果x和y已经属于同一个集合说明它们之间已经存在一条经过根的路径可以把x和y之间的相对关系算出来再断言它和题目给出的新关系是否一致。如果一致这条关系是正确的否则就是错误关系。如果x和y不在同一个集合说明这条关系是新信息要把两个集合合并起来同时根据给定的关系推导出被挂根节点到另一个根节点的权值。这就是带权并查集在处理“关系冲突判定”问题上的核心流程。4.3 核心代码与公式推导class WeightedDSU { private: vectorint parent, weight; public: WeightedDSU(int n) : parent(n), weight(n, 0) { for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] x) return x; int root find(parent[x]); weight[x] (weight[x] weight[parent[x]]) % 3; return parent[x] root; } bool unite(int x, int y, int rel) { // 表示x与y的关系为rel这里定义0同类1x吃y2x被y吃 int rx find(x), ry find(y); if (rx ry) { return (weight[y] - weight[x] 3) % 3 rel; } parent[ry] rx; weight[ry] (weight[x] rel - weight[y] 3) % 3; return true; } };这个公式怎么来我手把手推一遍。合并时把ry这棵树的根挂在rx下面也就是parent[ry] rx。问题变成ry到rx的权值weight[ry]应该等于多少才能保证节点y到rx的总关系与x到rx的总关系之差等于题目给定的rel。从y出发经ry再到根rx的总权值是weight[y] weight[ry]。从x出发经rx到根rx的总权值就是weight[x]。它们之间的差值需要满足(w[y] w[ry] - w[x]) % 3 rel解这个同余式(w[ry]) % 3 (rel w[x] - w[y]) % 3所以代码里写成(weight[x] rel - weight[y] 3) % 3加3是为了防止负数取模出现负值。这是带权并查集最容易写错的地方。每次合并前先梳理清楚自己定义的关系含义再套公式就不会翻车。find里的权值累加也要注意路径压缩时当前节点的父节点已经变成了根节点所以要用递归先找到父节点的根再在回溯过程中把父节点的权值累加到当前节点上。这就是为什么递归版find里必须先递归再累加。顺序反了weight就算错了。4.4 模运算与方向约定的坑我在竞赛和实验里见过不少人栽在同一类坑里关系定义方向没统一。比如你定义1表示x吃y合并公式里用的却是weight[y] - weight[x]结果答案全错。改个方向sign整个程序都要跟着改。最稳妥的办法是在写unite之前先在白纸上把三种关系画成有向图标清每条边的权值方向再对着画好的图写公式。另一个典型问题是多个关系叠加时忘记对3取模。比如weight[x]一路累加如果超过了3必须取模否则后面所有关系判断都会乱掉。取模的位置一个在find累加时一个在unite推导新权重时这两处缺一不可。还有一点食物链问题里经常出现“同一个节点同时给多条矛盾关系”的情况比如先说明A吃B又说B吃A。这不是并查集能自动识别的需要你在合并前先检查关系是否冲突。也就是unite函数里如果两个节点已经同根要先做断言校验校验失败立即返回false。这个分支逻辑不可省略。5. 实战中的坑排错与优化技巧5.1 递归爆栈与迭代写法基础并查集和带权并查集我优先推荐递归写法因为代码短、思路直白。但如果你处理的是超大图比如几百万个节点在极端数据下构造出一条极长的链递归find可能会踩爆系统栈。解决思路有两个。第一是改用按秩合并保证树高始终维持在O(log n)递归深度不会太大。第二是写迭代版find第一次循环找根第二次循环做路径压缩指向根。带权并查集的迭代版会更麻烦一些因为你要先记录每个节点原来的父节点再二次遍历时累加权值建议新手还是从递归入手遇到问题再优化。我个人的习惯是除非题目明确卡递归栈内存否则一律写递归。因为带权并查集迭代版出错概率实在太高。5.2 合并方向搞错的典型症状如果你发现查询结果时对时不对大概率是union或者unite合并方向出问题。比如第4节的公式里parent[ry] rx是有方向的如果写成了parent[rx] ry那么weight[ry]的推导公式也得跟着镜像翻转。忘了翻转就会产生逻辑错误。再比如树a的秩小于树b你把树a挂到树b下面是对的如果反过来并查集本身不会报错但树高会退化导致后续查询变慢。这类错误隐蔽性不强但排查起来没有头绪。我常用的调试方案是写一个暴力程序用真正的二维数组模拟连通关系然后随机生成操作序列对比并查集程序的结果。暴力解法虽然慢但作为金标准非常好用。数据规模不用大几十个节点跑几百轮就能暴露问题。5.3 面试中高频出现的并查集变体除了最基础的连通性问题和Kruskal还有几个变体值得提前准备。第一个是集合大小统计在并查集节点上额外维护sz数组合并时累加可以快速获取任意集合的大小。第二个是带删除的并查集。注意标准并查集是不支持删除一个元素的因为树结构里如果删掉某个节点它的子树会变得无家可归。现实需求里“把某个人移出群聊”的场景通常通过加一个“代理节点”实现为每个元素建立一个不会删除的外部节点元素本身挂在这个外部节点下面。删除时给这个元素重新分配一个新代理节点即可。第三个是可撤销并查集。它用于带“后悔”操作的问题需要把每次合并写入栈路径压缩会破坏可撤销性所以一般只做按秩合并不压缩路径。复杂度退化成O(log n)但仍然实用。这几个变体面试里问的频率逐步上升建议至少理解前两个。5.4 排查速查表症状大概率原因解决方法查询连通性结果不对parent数组未初始化初始化时parent[i] i缺一不可树退化、超时缺少路径压缩或按秩合并两个优化同时加带权结果时对时错weight累加顺序错find里先递归再累加合并后关系断言失败合并方向写反检查unite里rx和ry位置对照公式推出结论删除某个节点后集合混乱直接用普通并查集删除用代理节点方案递归爆栈树高失控或数据量极端用迭代find或按秩合并控制深度这些坑百分之八九十都能用“打印parent中间结果”的方式快速定位。我在调试带权并查集时会额外打印weight数组多数情况下几组小数据就能找到问题。6. 从工程实践到算法学习的几点体会如果你只是应付考试把基础并查集手写三遍再把带权并查集的食物链例题完整推导一遍基本就不会有问题了。但如果你像我一样在工程里真正用到并查集会发现它最大的价值不是“快”而是让代码逻辑变得非常干净。几个不同来源的连通关系几个相互独立的集合合并并查集都能用统一接口表达代码结构一目了然。有一个小技巧值得分享写并查集类时我会把find设计成公共方法把unite设计成返回bool值的方法。这样上层代码无论是做Kruskal、做闭环检测还是做关系断言都能直接复用不用每次都去判断“先查连通再合并”。这个小接口设计在很多竞赛模板和工程库里都能看到说明确实经历了实战检验。还有个个人习惯每学一种数据结构我都喜欢在笔记本上画一张它对应的“状态演化图”。比如并查集合并两个树时从两个根到新树每一步都画出来。遇到带权并查集边上的权值也画出来。图画明白了公式不用背代码也不会写错。这个习惯帮我解决过很多看似玄学的bug推荐你也试试。