1. 从业务问题说起一个合并查询并存的实际场景1.1 一个真实的后台需求几年前我维护过一个资讯类后台里面有个用户兴趣圈功能。规则很简单用户之间有关注关系只要 A 关注了 BA 和 B 就属于同一个兴趣圈关注关系会不断新增运营随时会来问这两个用户现在是不是同一个圈子的。用户量到了几十万量级关注关系接近百万条。第一次接到这个需求时我脑子里冒出的方案是 BFS/DFS用邻接表存图每次查询时从一个用户出发做遍历能走到另一个用户就说明同圈。听着没毛病但运营的高频查询一压进来就兜不住了。一次 DFS 要摊掉几十万节点查询一多系统直接跪。更麻烦的是新加一条关注关系后所有受影响分组的结论都要重新算整个方案的可扩展性太差。后来我换成了并查集问题立刻变得简单加关注关系就是合并查同圈就是看两个用户的根节点是否相同。每次合并和查询的代价都接近常数时间几十万用户、百万条关注关系跑起来毫无压力。这段经历给我留下的印象很深也是我在算法专题里专门留一篇讲并查集的原因——它不是一个只在面试题里出现的概念而是真实工程里处理动态分组连通性查询的一把顺手工具。1.2 问题的本质只有合并和查询没有删除如果把这个需求拿去套常见数据结构的套路会发现它有点特别。我们要维护的是若干个集合集合之间不断合并同时回答元素 a 和元素 b 是否在同一个集合。它不需要查集合里具体有哪些元素不需要支持从集合里移除某个元素也不需要把合并后的集合拆回去。这正是并查集Union-Find / Disjoint Set Union的定义域它只干三件事——初始化每个元素自成一组、按需合并两个组、查询两个元素是否同组。后面要讲的路径压缩和按秩合并两个优化是让这套逻辑在百万级数据下依然跑得飞快的核心。1.3 为什么很多人一开始容易绕进图算法的坑我后来带过几次新人发现大家拿到这种连通性问题第一反应几乎都是图遍历DFS、BFS、强连通分量。这不能算错但要注意图遍历回答的是一次性、全量的连通性问题比如给定整张图问有几个连通块而并查集擅长的是在线、增量的动态连通性边不断加进来查询随时发生。理解了这个区别选型时思路会清晰很多。如果硬用图遍历去实现动态不断加边 随时查询连通的需求每次加边后的全量重算成本是 O(NE)N 次操作最坏就是 O(NE)。并查集把单次操作压到接近 O(1)这就是它在这个问题域里不可替代的根本原因。2. 核心原理用一个数组维护的森林2.1 数组即父指针并查集最朴素的形式就是一个数组parent。parent[i]表示节点 i 的父亲节点如果某个节点的父亲是自己那它就是一个根。每一棵以某个根为祖先的树就代表一个集合。parent list(range(n))比如 n 6 时初始parent [0, 1, 2, 3, 4, 5]六个节点各自是根也就是六个集合。合并集合 0 和集合 1只需要让parent[0] 1。这时节点 0 的根是 1集合变成了五个。查找某个节点的根只要一直往上走到父亲等于自己的位置def find(x): while parent[x] ! x: x parent[x] return x合并两个集合就是找到两个根然后把其中一个根挂到另一个根下面def union(a, b): root_a, root_b find(a), find(b) if root_a ! root_b: parent[root_a] root_b可以把集合类比成公司组织架构每个员工只有一个直系上级顺着上级一路往上追溯就是大领导。判断两个员工是不是同一家公司的就看他们往上追溯是否是同一个人。这个类比能帮你把根的概念刻在脑子里后面看带权并查集时也更容易理解。2.2 路径压缩链式结构变菊花朴素版本的致命问题是树会越长越高。极端情况下如果合并顺序被构造得像一条链一次查找要往上走 O(n) 步。比如 0-1-2-3-4 这么一条父指针链find(0) 要沿着链走五次。数据规模一大性能立刻崩。优化手段是路径压缩在查找根的过程中顺手把沿途节点直接挂到根下面。递归写法非常优雅def find(x): if parent[x] ! x: parent[x] find(parent[x]) return parent[x]第一次 find 可能还要按原来的链多走几步但走完之后整条链被压平成一棵菊花——所有节点直接指向根。后续对这些节点的查找都是 O(1)。这就是懒的好处只在需要查询时做整理平时不动结构成本均摊到每次查询里。2.3 按秩合并让小树挂到大树光有路径压缩还不够因为在极端构造下路径压缩之前的树可能已经很高。虽然第一次 find 会把它压扁但递归深度和临时开销依然存在。更好的做法是在合并时控制方向永远把矮的树挂到高的树下让树的期望高度增长得慢一点。工程实现里有两种常用指标rank树的深度上界和size树的节点数。我个人更常用size它更直观——哪个集合人更多就让另一个根当它儿子。这样整体来看大集合不断吸收小集合树高通常不会超过对数级别。2.4 复杂度为什么被说成接近常数完整并查集路径压缩 按秩合并的单次操作时间复杂度是反阿克曼函数 α(n)它增长极慢。即使 n 是宇宙原子数量级别的输入α(n) 也不会超过 5。所以在工程上你完全可以把它当成常数时间使用。需要提醒的是单独只用路径压缩复杂度是 O(log n)单独只用按秩合并也是 O(log n)两个优化一起才达到 α(n) 这个级别。我在实际项目里基本永远两个都写上反正就多几行代码的事没必要赌数据是不是温和的。3. 手写一个并查集三版代码的演进3.1 第一版能跑的朴素实现面试或小数据量场景朴素实现可以直接用class DSU: def __init__(self, n): self.parent list(range(n)) def find(self, x): while self.parent[x] ! x: x self.parent[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra ! rb: self.parent[rb] ra这段代码逻辑正确但只适用于数据规模小、没有刻意构造链的场景。我曾用它写过一次性分析脚本跑几万条数据没有任何问题如果面对线上高并发查询就必须加优化。它的价值在于让你一眼看穿并查集的本质父指针数组 向上追溯。3.2 第二版递归 find 路径压缩class DSU: def __init__(self, n): self.parent list(range(n)) def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, a, b): ra, rb self.find(a), self.find(b) if ra ! rb: self.parent[rb] ra路径压缩让 find 的均摊复杂度接近常数。这里要注意递归实现存在递归深度上限问题Python 默认只能递归约一千层。如果树在尚未按秩合并的中间状态下被查询可能触顶。后面我会专门说这个坑和对应的非递归写法。3.3 第三版按秩合并 连通分量计数把两个优化都加上顺便维护一个集合数量count。这是我最常用的模板class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * n self.count n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] self.count - 1 return True def connected(self, a, b): return self.find(a) self.find(b)union返回False表示 a 和 b 本来就在同一集合合并失败。这个返回值在判环场景里非常有用下面会专门讲。count则可以直接回答当前还剩多少个集合——比如无向图的连通分量数或者连完所有边后还剩几个孤岛。3.4 边界与可调试性设计几个容易忽略的点。下标从 0 开始还是从 1 开始取决于题目数组长度要留对很多低级 bug 来自把下标直接当数量用。节点数量会超出初始范围时要么预分配足够大要么支持动态 appenddef add(self): self.parent.append(len(self.parent)) self.size.append(1) self.count 1 return len(self.parent) - 1为了调试方便可以加一个debug方法打印parent和size遇到问题直接看森林长什么样比凭空推理高效得多。另一个实用技巧是把find写成迭代版规避递归深度问题def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x这个写法每次循环把节点往上提一格达到隔代压缩的效果树高减半。在绝大多数场景下它和递归版效果一样但没有栈溢出风险。4. 带权并查集从是否同组到差多少/比例多少4.1 一个来自汇率兑换题的启发普通并查集只能回答你是否和我是一伙的。但生活里的关系往往带着量A 是 B 的上级B 是 C 的上级A 比 C 高几级1 美元能换 x 欧元x 欧元能换 y 日元1 美元能换多少日元这类关系可叠加传播的问题需要带权并查集Weighted DSU来处理。先想清楚模型给每个节点到它的父节点挂一个权值这个权值表示两者之间的相对关系比如A 相对 B 偏移多少。由于每个节点到根的路是确定的任意两个节点之间的关系都可以通过它们分别到根的值做差得到。4.2 权值如何跟 find 一起传播find 的路径压缩不再是单纯改父节点还要把沿途的权值累加起来。关键点是在递归压缩前先记住老的父节点递归拿到根之后把老父节点到根的权值加到当前节点上最后再做 parent 赋值。class WeightedDSU: def __init__(self, n): self.parent list(range(n)) self.dis [0] * n # dis[x] 表示 x 到 parent[x] 的偏移 def find(self, x): if self.parent[x] x: return x p self.parent[x] root self.find(p) self.dis[x] self.dis[p] self.parent[x] root return root错误的做法是先把parent[x]直接改成根然后才去累加dis。那样源头的坐标信息已经被截断后续权值全部错乱。这种 bug 非常隐蔽因为第一次 find 出来的结果可能是对的多压几次路径就乱了。4.3 union 的权重公式怎么来的假设要合并 x 和 y已知它们之间的偏移为 value也就是 x 相对 y 偏移 value。合并时先 find 出 rx 和 ry然后需要决定谁挂到谁下面并设置被挂节点的dis让整条链上通过异路径算出的关系与已知关系一致。以 rx 挂到 ry 为例设 x 到 rx 的偏移为dis[x]y 到 ry 的偏移为dis[y]dis[rx]表示 rx 到 ry 的偏移。那么 x 到 y 的偏移 dis[x] dis[rx] - dis[y]令它等于 value得到dis[rx] value dis[y] - dis[x]如果反过来让 ry 挂到 rx公式就变成dis[ry] -value dis[x] - dis[y]方向不同公式符号就不同这也是最容易被记混的地方。我的建议是不要背公式每次推导一遍或者画两个树写一遍。下面这个表格能帮你快速对照合并方向需要设置的权值推导思路rx 挂到 rydis[rx] value dis[y] - dis[x]dis[x] dis[rx] - dis[y] valuery 挂到 rxdis[ry] -value dis[x] - dis[y]dis[x] - (dis[y] dis[ry]) value4.4 完整例子除法求值LeetCode 399 是带权并查集的经典题。已知 a / b 2.0b / c 3.0求 a / c。把除法关系转成偏移量定义dis[x]表示 x 相对根的比例。这里不再用加法偏移而用乘法比例实现上调一下累加逻辑即可。class RatioDSU: def __init__(self, n): self.parent list(range(n)) self.ratio [1.0] * n # ratio[x] 表示 x 到 parent[x] 的比例 def find(self, x): if self.parent[x] x: return x p self.parent[x] root self.find(p) self.ratio[x] * self.ratio[p] self.parent[x] root return root def union(self, x, y, value): # value 表示 x / y value rx, ry self.find(x), self.find(y) if rx ry: return # 这里以 rx 挂到 ry 为例公式由 value 的语义推出 self.parent[rx] ry self.ratio[rx] self.ratio[y] * value / self.ratio[x]查询时如果 x 和 y 同根答案是ratio[x] / ratio[y]不同根则无解。这类题的通用套路是先把字符串节点离散化成整数再用带权并查集维护相对比例查询时做根关系判断。掌握了带权版本很多关系推断差分约束类题目都能顺手解掉。5. 实战踩过的坑与完整排查链路5.1 坑一递归 find 在极端数据下爆栈第一次写生成环境代码时我图省事用了递归 find没写按秩合并结果在一个被特殊构造的测试数据上直接RecursionError。Python 默认递归深度约 1000 层数据规模稍大很容易触发。排查链路先打印栈溢出时的查询下标再打印 parent 数组会发现某个根下面挂了一条很深的链。解决方案就是换成非递归版本先循链找根再走第二趟把沿途节点直接挂到根def find(self, x): root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! x: nxt self.parent[x] self.parent[x] root x nxt return root写到这里多说一句很多递归算法在工程化时都会遇到深度问题所以我在生产代码里对可能形成的树/链结构一律默认迭代实现。算法题里递归没问题不代表线上代码没问题。5.2 坑二路径压缩丢权重信息带权并查集里如果先把 parent 改成根再更新权值路径压缩就等于把中间节点的累计关系丢掉了。这种 bug 非常阴险代码逻辑看起来是只是多了一行赋值但权值全乱。排查链路构造一条三层链比如 0-1 偏移 11-2 偏移 1然后对 0 做两次 find核对每次dis是否等于暴力累加值很快能定位。这类问题靠看代码很难一眼发现靠小数据对照最快。我习惯在本地保留一个暴力版模拟函数随机造数据对拍两边答案不一致就说明优化版实现有问题。# 一次小规模对拍示例 for _ in range(10000): a, b, op random.randint(0, 5), random.randint(0, 5), random.choice([q, u]) ...对拍是个好习惯尤其对于带权并查集这种公式推出来但实现里容易符号写反的结构。不要相信自己的记忆力要相信可验证的对拍脚本。5.3 坑三union 公式方向记反合并时到底是用value dis[y] - dis[x]还是相反很多人靠背背了就忘。我自己记法是永远先假设 rx 要挂到 ry 下面把 x、y 各自到根的值代入统一公式推出来再写。推导过程上面已经给过这里不再重复。如果实在不想每次推可以把四个方向的公式整理到一张表里编码前对照。但我的核心建议还是理解推导。真正写业务代码时你面对的不会叫union(a, b, value)而可能是把这两个节点的关系记录为一对一映射公式一旦记错排查成本极高。5.4 遇到删除/拆集合怎么办并查集只支持合并不支持把边删掉或把一个集合拆成两个。业务里如果出现删除关注关系的需求离线处理是常见解法把操作顺序倒过来删除变成添加最后再把答案反转输出。举一个竞赛里常见的离线场景给一张无向图和若干次删边操作每次删边后问图有几个连通块。如果正着删并查集无能为力但如果先把所有删边操作执行完得到一个最终图然后从最后一次删边开始反向加边每加一条边就做一次 union查询结果记录下来最后反转输出问题就变成了纯并查集的活。这个时间倒流思想在动态连通性题目里非常常见。记住并查集不是万能的选型之前想清楚操作类型是否匹配能少走很多弯路。6. 并查集的典型应用地图6.1 连通块与孤立点统计最直接的应用统计一个无向图有几个连通分量或者添加若干条边之后还剩几个集合。这类问题直接套第三版模板union 返回 False 时连通块数不减少。典型例子是 LeetCode 的省份数量二维矩阵里isConnected[i][j] 1表示 i 和 j 直接相连问有多少个省份。还有岛屿数量、网络中的连通块统计本质上都是并查集的count维护。这类题用 BFS 也能做但并查集的编码量更小且天然支持边是动态加进来的变体。6.2 判环与最小生成树Kruskal 最小生成树算法按边权从小到大加边加之前判断两个端点是否已在同一集合。如果是同集合说明再加这条边就成环跳过否则合并。并查集就是 Kruskal 的地基没有它每加一条边都要全量查环复杂度会退化到无法接受。另一个常见题是冗余连接一棵树里多了一条边找出那条边。解法是按输入顺序加边第一次 union 返回 False 的边就是罪魁祸首。我在实际项目里也用过这种合并失败即冲突的思路比如批量导入用户关系时检测是否形成了环并查集一跑就出来不用写额外的图算法。6.3 等式满足性与关系冲突检测有个非常经典的题型给一堆等式约束比如a b、b c、c ! d问这些约束能否同时满足。做法是把所有关系先并起来然后检查所有!关系如果两个节点已经属于同一集合说明等式和不等式冲突直接返回 False。这个应用看起来不像图但本质上还是维护等价类并查集天然适合。6.4 动态加边与离线逆序处理除了前面提的删边逆序还有一种只加边、分批查询的场景。比如先给你一个空图然后依次加边每加完一批边就问一次连通块数量。这不需要离线直接在线处理即可每次加边做一次 union同时更新 count查询时直接读 count。如果查询里还夹杂着两个点是否连通那就再加一个connected方法每次 O(α(n))。这套组合在真实业务里非常常见比如微服务依赖关系检查、版本兼容性分组、批量任务依赖合并等。6.5 一点个人体会回到开头那个兴趣圈需求第一次用并查集跑通后我就意识到数据结构选型不是越复杂越好而是要看清楚操作的集合。只会合并、查询、不拆分的动态分组问题并查集就是最合适的答案。带权版本又把这个问题扩展到了关系可计算传播的类型。把这些基础结构吃透面对很多看似花哨的问题才会一眼看穿本质。最后再分享一个我自己的习惯任何并查集模板落地到具体项目前我都会先问三个问题——会不会有删除操作节点的范围会不会动态增长关系是否只有同组还是带有权值把这三个问题想清楚基本就不会选错版本。并查集看似简单但每一次简单背后都是对问题域的精确理解。