30 秒识别Q1 · 990 Satisfiability of Equality Equations：给一组形如 a==b、a!=b 的等式，判断它们能否同时成立。你的第一反应是哪个模式？
看答案
并查集。先把所有 == 合并成组，再逐条检查 != 的两端是否落在同一组。「约束是否自洽」= 连通性问题，两遍扫描解决。
两个动作：find（一路往上找老大，顺手做路径压缩）和 union（小的挂到大的下面）。两个优化都加上之后，单次操作近似 O(1)，代码一共十来行，属于必须能默写的那一档。
它相对第 10 章 DFS 的独门优势有两个：边是动态给的（DFS 得每次重跑），以及 union 返回 False 就等于发现了环——684、261 全靠这一行。
| 题面出现… | 想到 |
|---|---|
| 「有多少个连通分量 / 省份 / 朋友圈 / 组」 | 边全合并完，看还剩几伙 |
| 「加上这条边会不会形成环」 | union 返回 False 的那一刻（684） |
| 「判断这张图是不是一棵树」 | 边数 == n−1 且合并全程不成环（261） |
| 「把有共同元素的集合归并」（账户、邮箱、字符串） | 先把元素映射成整数 id，再合并（721） |
| 边是一条条流进来的，中途还要回答问题 | 并查集；DFS 得每来一条边重跑一次 |
| 「等式约束是否自洽」（a==b, b!=c） | 先合并所有相等，再检查不等（990） |
静态无向图数连通块，第 10 章的 DFS 更直接、也更好写；并查集的价值在「动态」和「成环检测」这两件事上。图是有向的、问的是顺序或循环依赖 → 拓扑排序（第 11 章）：并查集没有方向概念——union(a, b) 和 union(b, a) 只会让树形不同，「在不在一伙」的答案完全一样。带权最短路属于 Dijkstra，本书不覆盖。
■ 【骨架】 不变，闭着眼默写 ■ 【插槽】 随题变化，写题前先问自己填什么
class DSU:
def __init__(self, n):
self.p = list(range(n)) # 【骨架】一开始每个点自成一伙
self.size = [1] * n # 【骨架】按大小合并,防止退化成长链
self.count = n # 【插槽】要顺手维护的量:连通块数 / 每块大小
def find(self, x):
while self.p[x] != x: # 【骨架】
self.p[x] = self.p[self.p[x]] # 【骨架】路径压缩:顺手把爷爷认成爸爸
x = self.p[x] # 【骨架】
return 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.p[rb] = ra # 【骨架】
self.size[ra] += self.size[rb] # 【骨架】
self.count -= 1 # 【插槽】
return Truecount 顺手维护，连通块数就不用最后再数一遍。count 就是答案。面试里说得出「DFS 也能做，我选并查集是因为它顺手给出块数」即可。union 第一次返回 False 的那条边就是答案。题目要求返回最后出现的那条，而按顺序合并天然满足——这一点值得主动说明。n - 1，且合并过程中一次环都没成。少判任何一个都会漏用例（n-1 条边但有环 ⇒ 必然不连通）。edges。两道题一起做，能确认你写的模板对输入形式不敏感。while p[x] != x: x = p[x] 而不改 p[x]，最坏退化成 O(n) 的长链。self.p[x] = self.p[self.p[x]] 这一行不能省。union 的返回值没用起来——684、261、990 全靠「返回 False 说明已同组」。把 union 写成没有返回值的过程，这几道题就得另外再判一次环。n 个点、n 条边且连通，那是有环的图不是树。两个条件缺一不可。{邮箱: id} 映射。把 p 换成字典虽然也能跑，但 size 数组和路径压缩都要跟着改写，容易出错。30 秒识别Q1 · 990 Satisfiability of Equality Equations：给一组形如 a==b、a!=b 的等式，判断它们能否同时成立。你的第一反应是哪个模式？
并查集。先把所有 == 合并成组，再逐条检查 != 的两端是否落在同一组。「约束是否自洽」= 连通性问题，两遍扫描解决。
30 秒识别Q2 · 839 Similar String Groups：若两个字符串相等，或交换其中两个字母后相等，则它们相似。求相似字符串的组数。你的第一反应是哪个模式？
并查集。两两判断相似（O(n²·len)）后合并，最后数连通块。「归组 / 有多少组」是并查集最直白的暗号，和 547 是同一道题换了个判定条件。
30 秒识别Q3 · 207 Course Schedule：共 n 门课，给出若干「先修 A 才能修 B」的关系，判断能否修完所有课。你的第一反应是哪个模式？
拓扑排序，不是本章——边是有向的。并查集里 union(a, b) 和 union(b, a) 给出的连通性完全一样，天生表达不了「谁在谁前面」，自然也判不出有向环。见 §2 分流条件。
每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。