如果你刷过算法题或者接触过网络连通、图像分割、Kruskal 最小生成树这类问题一定绕不开一个代码量小到让人低估它的数据结构并查集。我第一次在教材里看到并查集三个字时觉得它不就是维护一堆父节点指针吗后来在实际写代码时才明白它能在近乎常数的复杂度内回答两个元素是否属于同一个集合还能在动态合并集合的过程中持续维护这种关系。这个能力在数据结构与算法里属于短小精悍的典型无论在考研 408、LeetCode 刷题还是工程实践中出场率都非常高。这篇文章我会从最朴素的实现讲起逐步讲到路径压缩、按秩合并再到很多人觉得头疼的带权并查集最后把实际写代码时容易踩的坑列一遍。全程都用大白话尽量让没系统学过数据结构的人也能上手同时给已经会基础用法的读者补上为什么这么写的底层逻辑。你不需要刻意背模板理解了设计思想代码自己就能写出来。1. 并查集到底在解决什么问题从拉群到找代表1.1 一个生活化的比喻微信群与共同好友先别急着看代码想一下这种场景你有好几个微信群每个群里有不同的人。刚开始大家各自成组后来有人把群 A 和群 B 合并成一个新群再后来你遇到一个新朋友你想知道他是不是你已经认识的人或者说他和某个群里的某人是不是同一个人脉圈子你要做的其实是两件事合并圈子、查询两个人是否在同一个圈子里。这正是并查集的核心操作。它支持两种操作find(x)找出 x 所在圈子的代表union(x, y)把 x 和 y 所在的圈子合并成一个。数据结构学的术语叫等价关系维护说人话就是动态管理分组。很多问题表面上不是这个形态但只要抽象成集合合并 是否同组查询基本都能用并查集来解。1.2 核心模型用一棵树来代表一个集合并查集内部通常不真的去存这个集合有哪些元素而是给每个元素一个父节点指针形成一棵树。每个集合就是一棵树树的根节点就是整个集合的代表元素。find(x)就是顺着父节点一路往上走直到找到根union(x, y)就是把 x 所在树的根接到 y 所在树的根下面让两棵树变成一棵。为什么用树而不是直接给每个元素标个组号因为集合合并后如果标组号你要把某个组的所有元素挨个改一遍改成新组号。元素一多这个操作就是 O(n) 的。树结构的好处是合并永远只改一个根节点的父指针代价只有 O(1)查询的时候再顺着路径找根。虽然查一次可能要爬很多层但配合后面要讲的优化可以做到几乎 O(1)。1.3 为什么不用数组直接记组号有人会问那我维护一个数组group[x]表示 x 所属的组号查询确实 O(1) 啊。问题出在合并上假设组 A 有 10 个人组 B 有 10 个人合并时你不得不把其中一组所有人的group值改成另一组的号这就是 O(10) 的代价。极端情况下反复合并总代价很容易变成 O(n²)。所以并查集这种只改一个父指针查询时临时找根的方案实际上是用查询的一点点开销换取了合并的高效率整体复杂度非常优秀。这里还要强调一个细节初始时每个元素单独成集合所以fa[x] x每个节点是自己的根。一旦代码里忘记初始化这个自环后面find会直接越界或者死循环这是新手最常踩的第一个坑。2. 基础实现与两个关键优化让并查集真正变快2.1 先写一个能跑的朴素版本先用 Python 写一版最直白的实现目的是看清楚逻辑class DSU: def __init__(self, size): # 初始化每个节点的父节点指向自己 self.fa list(range(size)) def find(self, x): # 循环找根根的特点是 fa[x] x while self.fa[x] ! x: x self.fa[x] return x def union(self, x, y): # 合并 x 和 y 所在的集合 rx, ry self.find(x), self.find(y) if rx ! ry: self.fa[ry] rx这个版本逻辑没错但有一个明显的问题如果每次合并都让一棵树挂到另一棵下面而且挂的方向一直不控制树可能变成一条长链。比如依次执行union(0, 1)、union(1, 2)、union(2, 3)最后会发现 0 是根3 一路查到 0 要走三步。数据量一大每次find都接近 O(n)整个并查集就废了。所以下面马上引入两个经典优化这也是学习并查集的重头戏。2.2 路径压缩让每次查找都把路压扁路径压缩的思想特别简单在find(x)从 x 到根的过程中把沿途经过的所有节点的父节点直接改成根。这样以后再查这些节点一步就能跳到根。递归写法是这样的def find(self, x): if self.fa[x] ! x: self.fa[x] self.find(self.fa[x]) return self.fa[x]如果你担心 Python 递归层数过高也可以写成迭代版先找根再把路径上的节点全部改挂到根下def find(self, x): root x while self.fa[root] ! root: root self.fa[root] while self.fa[x] ! root: nxt self.fa[x] self.fa[x] root x nxt return root路径压缩之后树的高度会变得非常小绝大部分节点都直接挂在根上查找时间大幅下降。我建议初学阶段先用递归版理解它为什么能改变结构等真正做工程或写大数据量代码时再考虑迭代版避开递归风险。2.3 按秩合并让小树挂到大树上路径压缩解决的是查询时变快但合并方向上如果不加控制仍然可能出现短暂退化明明可以让矮树挂高树结果你让高树挂矮树树反而长高。按秩合并的思路是记录每棵树的深度或大小合并时总是把深度小或元素少的树挂到深度大或元素多的树下面。用集合大小当秩的实现最简单class DSU: def __init__(self, size): self.fa list(range(size)) self.sz [1] * size def find(self, x): while self.fa[x] ! x: self.fa[x] self.fa[self.fa[x]] x self.fa[x] return x def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return if self.sz[rx] self.sz[ry]: rx, ry ry, rx self.fa[ry] rx self.sz[rx] self.sz[ry]这个union里先比较根节点所在集合大小确保总是把小的挂到大的下面。这样树高不会超过 O(log n)再叠加路径压缩两者合在一起的摊还复杂度是反阿克曼函数 O(alpha(n))。alpha(n) 增长极其缓慢实战中可以认为一次 find 就是常数时间。这也是并查集能在 ACM、LeetCode 大量题目里成为万能工具的根本原因。2.4 两个优化会不会冲突这个问题我经常被问到。路径压缩会改变树的高度所以如果sz还是当初按合并时的那个数其实已经不完全等于实际树深了但没关系。按秩合并并不需要精确的当前高度它只需要一个单调递增的近似高度来避免合并方向失控。即使路径压缩把树压扁了sz依然指导我们尽量别把大树挂到小树下。所以在实际模板里用集合大小当秩是最稳的选择。这里还有一个经验如果你知道自己所有union操作都已经在代码里做了find那么其实路径压缩已经能让大部分树保持扁平即使不写按秩合并绝大多数情况也能跑得很快。但严谨的复杂度证明需要两个优化配合竞赛或者考试里需要写得规范工程里我也建议都写上多几行代码换万无一失很划算。3. 带权并查集不仅能判断是否同组还能算出差多少3.1 带权的本质父指针边上多存一个数基础并查集只能回答是否同一个集合但现实问题往往要求更多。比如我们有若干未知变量告诉你某两个变量之间存在差值关系然后不断添加新的差值关系同时询问两个变量之间能不能算出差值、差多少。这个场景就是带权并查集最典型的应用。实现上在原有fa[x]旁边加一个数组d[x]表示 x 到fa[x]的权值。这个权值具体含义由问题定义常见的有两种一种叫差值比如d[x] x - fa[x]另一种叫模意义下的关系偏移比如用 0、1、2 表示同类、吃、被吃。路径压缩的时候d[x]要同步累加让d[x]变成 x 到根节点的权值合并的时候需要根据题目给出的关系方程反推出根节点之间应该赋什么权值。3.2 合并公式手把手推导用一个简洁模型来说明假设d[x]表示 x 比fa[x]大多少即d[x] x - fa[x]。已知一条新关系x - y val且当前 x 所在的树根是rxy 所在的树根是ry。我们要把rx接到ry下面并求出newd[rx] rx - ry应该等于多少。先展开等式x - y (x - rx) (rx - ry) (ry - y)路径压缩后d[x] x - rxd[y] y - ry。注意x - rx就是d[x]ry - y是-d[y]因此val d[x] newd[rx] - d[y]移项得到newd[rx] val d[y] - d[x]如果你要反过来把ry挂到rx下面类似推导会得到newd[ry] -val d[x] - d[y]代码里直接按上面公式写就行。关键在于不要把d的方向搞反统一约定成节点到父节点的差值永远不会错。3.3 一个完整代码示例维护变量之间的差值关系下面给一个可以跑通的带权并查集模板class WeightedDSU: def __init__(self, size): self.fa list(range(size)) self.d [0] * size # d[x] 表示 x 到 fa[x] 的差值 def find(self, x): if self.fa[x] ! x: root self.find(self.fa[x]) self.d[x] self.d[self.fa[x]] self.fa[x] root return self.fa[x] def union(self, x, y, val): # 表示 x - y val rx, ry self.find(x), self.find(y) if rx ry: # 如果已经同组可以检查是否矛盾 return (self.d[x] - self.d[y]) val, None # 按秩可以省略这里假设直接把 rx 挂到 ry self.fa[rx] ry self.d[rx] val self.d[y] - self.d[x] return True, ry这里find递归版需要注意执行顺序先递归找根再把权值从旧的fa[x]转移到新根路径上。很多初学者会先改fa[x]再累加d[x]结果算出来全是错的。正确顺序是先记录旧父节点递归找根然后累加权值最后挂到新根。当两个元素已经在同一集合时可以直接通过d[x] - d[y]判断它们是否满足新给出的差值从而检查矛盾。这个能力在系统中有多条约束判断是否冲突的场景特别有用比如并查集版本的差分约束或者判断若干判断语句的真伪。3.4 扩展到模关系食物链题的通用解法把差值模型整体加到模 K 意义下就得到了带权并查集最常见的竞赛形态。拿经典的食物链题举例三个物种 A 吃 B、B 吃 C、C 吃 A。每个节点与根的关系用 0、1、2 表示通常定义d[x]是 x 到父节点的偏移量。每句话给出两个动物的关系同类或捕食其实就是给出一个目标偏移关系。合并时把上面推导出的公式整体对 3 取模就能得到如下更新self.d[rx] (val self.d[y] - self.d[x]) % K这里 val 指 x 与 y 在模 K 意义下的关系。做完之后如果两个节点已经在同一棵树里判断(d[x] - d[y]) % K是否等于题目给出的 val就可以识别这条话是否为假。这种方法本质上是把相对关系当成一种路径上的距离路径压缩时累加合并时按方程反推。理解了差值模型再去看食物链、奇偶游戏这类题你会发现它们在代码上几乎没有区别差别只是val和K的含义。4. 并查集最常见的应用场景与实战案例4.1 Kruskal 最小生成树并查集最经典的搭档说到并查集的最大应用一定是 Kruskal 算法。Kruskal 的思路很简单把所有边按权重从小到大排序挨个判断这条边会不会形成环能选就选。如何判断是否形成环只要看边的两个端点之前是不是已经连通。这正是并查集的find操作。一个简化版流程是edges.sort(keylambda e: e[2]) dsu DSU(n) ans 0 for u, v, w in edges: if dsu.find(u) ! dsu.find(v): dsu.union(u, v) ans w这里find判断是否连通union把新边连起来。如果没有并查集每次判断连通都要遍历图一次复杂度不可接受。有了路径压缩加按秩合并整个 Kruskal 的复杂度基本被排序主导这也是面试和考研里常考的复杂度分析点。4.2 网格与像素连通把二维坐标映射成一维编号在图像处理里经常需要判断某几个像素是否连成一片。比如做连通域标记我们扫描每个像素如果它和左边或上边的像素属于同一块区域就用并查集把它们合并。这类问题的技巧是把二维坐标(x, y)映射成一维编号通常用x * cols y。然后对所有相邻且满足合并条件的像素对执行union。一个常见套路是扫描时只查看左边和上边的邻居因为你从左到右、从上到下扫描右边的和下边的还没处理等扫到它们时自然会和当前节点合并。这样每个像素最多合并两次总共 O(n) 次操作速度非常快。处理完之后统计fa[i] i的根节点数量就是连通区域的数量想合并更多额外条件比如颜色差异小于阈值也只是一个if的问题。4.3 离线动态连通性回答此时它们是否相连有些场景是不断加边不断询问两个点是否连通。这种问题用并查集处理再合适不过。因为并查集只支持加边合并不支持删除边所以如果全是加边操作按时间顺序处理即可。如果你想处理删除边的逆问题常用套路是把整个过程离线反转先处理出最终状态然后从最终状态往前撤销删除变成不断加边这样又回到了并查集的舒适区。这个方法在竞赛题里叫逆向并查集非常实用。举个工程里的例子数据库某个配置在运行中被反复修改你想知道某几个服务最终是否处于同一个配置组就可以离线处理。4.4 回到热搜词并查集主要用来做什么的我看了下网上关于并查集的搜索词问得最多的就是这句。你直接搜答案可能会看到一堆维护动态连通性之类的定义但真正理解它做什么还是要落到具体场景。一句话回答并查集用来维护若干元素之间的动态等价关系。这里动态强调它可以随时合并集合等价强调元素之间要么同组要么不同组这种关系具有传递性A 和 B 同组B 和 C 同组那 A 和 C 一定同组。所有满足这种传递性的问题从朋友圈分组、网络设备连通到像素聚类、数据库分区归属本质上都可以用并查集。5. 我从刷题和工程里踩过的坑与检查清单5.1 高频手误find 写错方向我自己刚开始写并查集时最常犯的错就是find里循环条件写反。早期代码是while self.fa[x] x: x self.fa[x]这会导致find永远停在原位置然后union里两个根判断失效最后数据全乱。正确逻辑是当fa[x] ! x时继续往上走。这个错误在递归实现里表现为没有return在迭代实现里表现为死循环。另一个高频错是union时忘了先find根直接把fa[x]改成y。这样如果 x 不是根合并后整棵子树被挂到 y 下面原集合里其他节点就会丢失产生脏数据。记住union合并的一定是根不是任意节点。5.2 带权并查集的三个隐蔽问题带权并查集除了找根还要处理权值累加这里最容易出问题一是find递归里权值累加顺序。一定先把旧父节点的权值加进来再更新fa[x]。如果在fa[x]变成根之后才去取d[self.fa[x]]取到的已经是新的根的值结果必然错误。二是取模之后出现负数。在模 K 环境下写出self.d[rx] (val self.d[y] - self.d[x]) % K之后如果括号里是负数很多语言里%仍然是负数。稳妥做法是(expr K) % K或者统一写成((val self.d[y] - self.d[x]) % K K) % K。三是权重方向。同一个题目里你必须从头到尾坚持一种方向定义比如d[x]是 x 到fa[x]的关系还是fa[x]到 x 的关系。一旦在两条更新公式里混用判断条件基本全错。建议每次写带权并查集前先在注释里写下方向和数学关系不要省这几分钟。5.3 调试技巧怎么快速验证并查集写对没有在工程项目里我习惯写一个简单的检查函数把所有元素打出来看看每个节点的fa和d是否符合预期。尤其是带权并查集只盯着单次操作很难发现问题。可以构造一个小的数据集比如 3 个元素手动执行两次union然后打印根和权值和手算结果对照。更高效的验证方法是暴力对拍另外写一个用数组存原始关系的模拟逻辑随机生成一堆union和查询拿暴力方法和并查集结果对比。只要规模不大一轮随机测试就能暴露问题。这个方法对面试复习、竞赛调试都很好用比看半天代码肉眼纠错效率高得多。5.4 生产环境的模板建议迭代版路径压缩如果是写生产代码我的建议是优先用迭代版路径压缩避免极端输入导致递归栈溢出。Python 默认递归深度差不多一千左右遇到一棵长链退化树时递归find可能直接崩溃。迭代版的思路是两遍循环先找根再沿路径把所有节点直接指向根。代码稍长但稳定性更好。如果你用 C递归深度问题一般没那么明显但也要留意深度。很多 C 模板直接写递归版find配合按秩合并已经足够因为树高被限制在 O(log n) 量级不会栈溢出。Python 不开sys.setrecursionlimit的话还是迭代版更安心。最后再分享一个小技巧在写并查集之前先想清楚两个元素之间的关系是什么能不能用整数偏移表达。如果能就考虑带权并查集如果只用同组/不同组普通并查集加两个优化就够。别一上来就套高级模板简单问题保持最简单这是我在实际写代码里摔过跟头才明白的道理。