刷LeetCode的时候我习惯把每道题的耗时都记下来。这道990题我首次完整跑通花了将近100分钟。说实话这个时间不算短但复盘下来真正写代码只占了一小部分更多的时间花在了“这题为什么能用并查集”以及“不等式到底怎么处理”这两个问题上。后来我把这100分钟拆开看发现其中至少40分钟都是在用错误的思路试探边界。这篇文章就围绕LeetCode 990这道“等式方程的可满足性”展开重点不是贴一份能通过的代码而是把我踩过的坑、想通的逻辑、以及为什么最终选择并查集这个方案完整地梳理一遍。如果你刚好刷到这道题或者在做图论、并查集相关的练习这篇文章应该能帮你省下不少走弯路的时间。1. 题目到底在说什么读懂“等式方程的可满足性”1.1 为什么说它是“可满足性”问题先看题目的原始描述给出一组由小写字母组成的等式或不等式方程每个方程长度固定为4形如ab或者a!b。你需要判断是否存在一组整数赋值能让所有这些方程同时成立。如果能返回true否则返回false。我第一次看到“可满足性”这三个字脑子里的第一反应是“SAT问题”。但冷静下来看这里的变量并不是布尔值而是可以取任意整数的小写字母变量。每个变量本质上可以是任意一个整数那么约束的本质就变成了哪些变量必须相等哪些变量必须不相等。例如[ab,bc,a!c]第一眼看上去没问题但如果你把ab和bc连起来看就会得到ac。此时又出现一条a!c这就互相矛盾了。所以这组方程是不可满足的应该返回false。这题的“可满足性”不在于给每个变量具体赋什么值而在于约束之间会不会产生冲突。真正要回答的问题是这些方程内部存在矛盾吗1.2 三种读法等于、不等于、传递我试着把方程拆成三类看待这样后面写代码时思路会清晰很多。第一类是等式形如ab意味着变量a和变量b必须取值相同。第二类是不等式形如a!b意味着变量a和变量b的取值必须不同。第三类是隐含关系也就是通过等式传递出来的新关系。比如ab且bc那么三条变量a、b、c全部等价它们归属于同一个集合。对同一集合里的两个变量而言它们必须是相等的。如果题目又给出它们!那就违反了集合的一致性。这个思路是整道题的核心先用等式把所有变量划分成若干个“等价类”然后检查每条不等式看不等号两边的变量是否落在同一个等价类里。可以类比一下现实中的场景等价类就像朋友圈里的群组群里的每个人都必须是朋友关系。现在规则是“群内互相认识、跨群不认识”但同时又有一条规则说“某两个人必须不认识”如果这两个人恰好又在同一个群里规则就崩了。2. 解法选型为什么这道题被公认为并查集练手题的入门首选2.1 暴力尝试会遇到什么问题如果不用专门的数据结构凭空解这道题很容易会想到一个方向把等式当成无向图的边变量当成节点。所有等式连接起来的连通分量就是必须取同样值的节点集合。然后对每条不等式做检查看两端的节点是否已经在同一个连通分量里。那么问题就变成了怎么高效地维护“连通分量”。最笨的方法是用邻接表存图等式建边之后跑一遍 DFS 或 BFS把每一个连通分量打上编号。样例少的时候这个办法是能跑的。但问题在于如果等式数量很多n最大可以到 500每次重新构图再遍历的开销并不算小代码写起来也比较啰嗦。另一种暴力的方式是直接维护“等价关系表”。初始化时认为每个变量只和自己等价。遍历等式时把两个变量所属的等价类合并。这个思路本质上已经是在手写一个简化版的并查集了。你要是想纯粹用哈希表加集合来做也能做但合并两个集合时要把其中一个集合里的所有元素搬到另一个集合里最坏情况下会退化成 O(n^2)。对于这道题 500 条方程的数据量虽然不至于超时但作为一个专项练习这种做法的扩展性太差了。2.2 并查集为什么恰好契合等式的传递性并查集这种数据结构天生就是来维护“传递性”关系的。它有两个核心操作find找出某个元素所属集合的根节点union把两个集合合并成一个集合。如果用并查集来处理这道题等式ab就直接翻译成union(a, b)。当所有等式都合并完之后再检查不等式a!b本质上就是看find(a)和find(b)是否相等。这个逻辑和题目内在结构是严丝合缝的。等式具有自反性、对称性、传递性正好是等价关系而并查集就是最经典的等价类维护工具。如果题目改成不等式需要传递比如a b且b c那就不是并查集能直接解决的问题了需要考虑拓扑排序或者差分约束。所以先看到等式再想到并查集这个联想链条应该是每个刷题的人都该建立的。2.3 两种图论思路的对比清单我把 DFS 连通分量法和并查集法放在一起做了个对比方便你做选择维度DFS/BFS 染色法并查集法核心思想构图后跑遍历给连通分量编号维护等价类直接合并根节点时间复杂度O(n m)m 是等式边数近似 O(m α(n))α(n) 为反阿克曼函数代码量偏长需要递归遍历邻接表核心约 20 行路径压缩/按秩合并不需要两个优化都可以做适合的后续扩展适合求具体连通分量编号更适合频繁合并和查询的场景就这道题来讲DFS 也能通过但你多写代码之后会发现并查集的实现几乎不需要动脑把模板写熟后面遇到大量“判断两点是否连通”的题都能直接用。两者都在 LeetCode 热门100题相关练习中经常出现真心建议把并查集版本写熟练。3. 从零实现并查集核心细节与整体实现步骤3.1 并查集的基本操作与关键优化先说明基础版本。因为我们这里变量只有 26 个小写字母可以固定开一个长度为 26 的数组下标 0 对应字母a依此类推。初始化时每个变量的父节点是自己代表每个变量单独成一个集合。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1find里用的路径压缩是“隔代压缩”它会把当前节点直接指向父节点的父节点虽然不如完整递归压缩那么彻底但效果已经很接近。使用递归写更短的版本也可以def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]递归写法更直观唯一的风险就是递归深度但这里总共才 26 个节点完全没有压力。两个版本选一个重点是要保证每个union操作之前都调用find否则可能把非根节点合并导致集合信息错误。3.2 先处理等式再验证不等式整体实现解析整体的实现框架其实只有两步但这两步的顺序不能反。先过一遍所有等式把它们合并到同一个集合中再从头检查所有不等式只要发现两端的变量已经在同一个集合里就说明出现了矛盾直接返回false。为什么必须先把等式全部处理完再检查不等式你可以想象一种交错出现的输入场景比如[ab,b!c,ca]。如果每读一条方程就立刻判断不等式处理到b!c的时候b和c确实不连在一起于是暂时通过继续处理到ca时把c和a合并到一起而a早就和b合并了于是最终集合里实际上变成了a、b、c三合一回头再看b!c就已经冲突了。如果不先完成所有等式合并这种迟来的矛盾就会漏掉。另外要注意的是一个变量可以出现在多个不等式里并且不等式的两个端点未必在当前等式约束中已经出现比如[ab,c!d]。这里c和d没有出现在任何等式里那它们各自独立成集合因为find(c) ! find(d)所以不等式是成立的结果返回true。这种变量也要参与初始化好在题目规定都是小写字母天然只有 26 个不会存在未知变量的情况。用两个循环实现核心逻辑def equationsPossible(equations): uf UnionFind(26) # 第一遍处理所有等式 for eq in equations: if eq[1] : x ord(eq[0]) - ord(a) y ord(eq[3]) - ord(a) uf.union(x, y) # 第二遍检查所有不等式 for eq in equations: if eq[1] !: x ord(eq[0]) - ord(a) y ord(eq[3]) - ord(a) if uf.find(x) uf.find(y): return False return True有两点觉得值得单独拿出来强调。第一eq[1]是等号或不等号的第一个字符比如ab中eq[1]是a!b中eq[1]是!直接用判断比较省事不需要关心eq[2]因为等号不会出现ab这种非法形式。第二方程格式固定为 4 个字符eq[0]是左边变量eq[3]是右边变量。这种字符串处理技巧在处理固定格式输入时很常见四两拨千斤。3.3 用数据说话这题的时间复杂度为什么能过分析一下这个方案为什么能在 LeetCode 上稳定跑过。先看时间复杂度。假设方程总数为m题目给的范围是m 500。第一遍处理等式时每条等式调用一次unionunion内部会调用两次find而find经过路径压缩和按秩合并优化后单次操作的均摊时间复杂度接近 O(1)。所以第一遍的复杂度是 O(m α(n))。第二遍处理不等式每条不等式调用一次find单次也是近似常数。两个循环合起来仍然是 O(m α(n))实际运行非常快。空间复杂度呢因为变量是小写字母所以只需要一个固定大小 26 的数组和 rank 数组空间复杂度是 O(1)。如果题目把字母范围改成大写字母或者数字那就要注意数组的扩容了。再对比一下另一种常见做法——把每条等式当作约束用哈希表存集合。这个方法最坏情况下每合并一次都要把一个集合里的元素逐个搬去另一个集合单次操作是 O(k)k是当前集合元素个数。虽然 26 个节点让最坏情况显得无所谓但如果你把同样的思路迁移到几百万个节点的场景就会有明显的性能差距。这就是“为什么竞赛代码常用并查集而不是朴素集合”的根本原因。3.4 扩展练习把同一个模板迁移到其它题目并查集模板一旦写顺能解决的题就不只是这一道了。我把做过的几道高频题列出来你可以直接拿来做迁移练习LeetCode 547 省份数量给一个邻接矩阵要求统计连通分量的数量。初始时每个人是一个省份如果两个人直接或间接相连就合并。最后遍历所有节点统计根节点等于自己的个数。LeetCode 200 岛屿数量虽然不是最典型的并查集题但也能用并查集做扫描每个格子时如果右边或下边是1就执行一次合并。不过这道题用 DFS 更直观用并查集会稍微绕一点。LeetCode 684 冗余连接给一棵多了一条边的树要求删除那条让图形成环的边。边遍历边合并如果某条边的两个端点已经在一个集合里说明这条边就是多余的。LeetCode 1319 连通网络的操作次数要求算出最少要调整几根线才能让所有电脑连通。先合并已经连通的线然后数一下还有多少个独立的连通块。你只要把这一类题各做一道对并查集的理解会比只看一道题深刻得多。我个人的建议是先手写一遍 990再尝试 684最后反过来看 547因为 547 的矩阵输入方式会让你重新思考“如何把二维下标映射到一维”。4. 刷题过程中的真实问题与排查技巧4.1 我写代码时踩过的坑上第一次提交时我犯了一个比较隐蔽的错误在检查不等式的循环里我没有调用find而是直接比较了parent[x]和parent[y]。当集合结构是两层以上时比如经过union(0, 1)和union(1, 2)后0的父节点可能是11的父节点是2此时直接比较parent[0]和parent[2]会得到1 ! 2从而错误地认为0 ! 2是成立的。正确写法永远是先调用find拿到根节点再比较。这个问题非常经典在并查集相关的所有代码里都值得警惕。第二个坑是关于变量映射的。有些题解会把字母直接转成ord(c) - ord(a)有些题解则用字典做字母到索引的映射。如果图省事直接用了ord(c) - 65虽然也能运行但可读性差而且一旦题目换成了大写字母或包含数字很容易写错。关键是不要硬编码65要写出能传达意图的代码。还有一次出错是因为我在合并集合时没有判断两个根是否已经相同。逻辑上如果两个元素已经在同一个集合里再调用union不应该产生任何变化。但如果没有加根节点相等的判断就直接执行按秩合并可能会把parent指向自己从而造成死循环风险。虽然这道题规模小不容易触发但在更大规模数据下就是定时炸弹。所以我在union开头保留if rx ry: return这一步绝对不省。4.2 调试技巧如何快速定位失败的样例写完之后如果没过不要急着往代码里乱打日志。我的调试方法很简单构造三个小用例先跑通逻辑再定位问题。第一个用例是[ab,ba]这是最基础的等式合并结果显然是true。如果这个用例挂了那八成是union或者字符串解析出了问题。第二个用例是[ab,b!a]同样的变量在等式和不等式里打架结果必须是false。第三个构造要稍微复杂一点用[ab,bc,c!a]来测试传递闭包是否形成。如果前两个用例都过了第三个出了问题那说明问题不是出在解析而是出在并查集的路径压缩没有生效或者在不等式检查前没有完成全部合并。如果有 LeetCode 的调试环境可以直接在本地跑一个测试脚本把所有用例打到一个列表里循环执行观察哪个输出和预期不符。比在网页上反复提交要高效得多。刷题这么多年我觉得一个能快速构造用例的好习惯比记住所有边界条件都有用。4.3 常见问题速查表我整理了一份关于这道题的常见问题速查表基本都是群里和评论区问得比较多的问题现象可能原因修复方式一边写一边写!会漏判第一遍没有先合并所有等式先扫所有等式再扫所有不等式错误地直接比较parent[x]树深度大于 1 时parent不是根改成先调用find(x)union出现死循环没有判断两个根是否相同在union开头判断rx ry字母转下标用固定 ASCII 值可读性差且容易出错用ord(ch) - ord(a)以为a!b能传递混淆了等价关系与非等价关系不等式不进并查集只做检查没有初始化 26 个节点部分变量可能未在任何等式出现父节点默认设为自身即可我不推荐在排查时去翻大量题解对比那样容易把自己的思路带偏。更好的顺序是先自己写一版能过的代码然后去评论区看看别人的只读优化比如有人用size数组代替rank数组有人用递归式find代替迭代式find这些都属于风格差异不影响正确性。5. 这类问题在更大场景中的应用与个人做题心得5.1 从等式的并查集到更广的连通性问题有人可能会问这道题只是一个刷题训练跟真实项目有什么关系其实“等价关系维护”在现实工程里出现频率并不低。举几个场景。在数据库 schema 迁移场景里不同的表字段可能因为外键关系形成一串等价依赖如果你需要判断两个字段最终是否指向同一张底层表可以用并查集做别名解析。在分布式系统里节点可能通过配置组、环境变量等方式被赋予多个别名判断两个别名是否属于同一个物理节点本质上就是等价类查询。在社交网络的好友推荐、风险控制里的设备指纹归并等场景中也需要不断把碰撞出的相同设备合并成同一个设备画像。这些场景的数据量远不止 26 个节点通常会有几十万甚至上百万但并查集的均摊复杂度依然能扛得住。只要保证初始化把所有可能出现的节点都纳入并且每次操作后都用find收敛路径这套模板可以直接在业务代码里复用。我自己在做数据清洗的时候也常常会用这个模式解决“同一实体多条记录合并”的问题提前写好祖先数组比反复用 SQL 做内连接要灵活得多。5.2 关于“耗时100”的个人复盘心得回到标题里那个“耗时100”。如果只从结果看100 分钟解一道题确实不算快但这种慢更多来自思考方式的切换而不是代码能力不足。我在前 20 分钟尝试用哈希表模拟集合在合并时反复搬运集合元素代码又长又容易错。后来意识到用并查集差不多 20 分钟就能写完并跑通样例。剩下的时间都花在验证“不等式为什么不能先处理”这类边界情况上。我个人体会是这种“耗时”反而很有价值。如果你能在一道题上想清楚一个核心数据结构选型比快速跳过十道同类型题更能建立长期记忆。现在我做并查集相关的周赛题基本能在一分钟内判断该不该用这个结构。这就是反复复盘带来的感觉。再给一个小技巧做完这题之后可以把equationsPossible作为模板函数存进自己的代码片段里下次遇到“判断多个约束是否能共存”的题时先拿出来改改效率会提高很多。这比每次都从空白文件开始写要舒服得多。