题干与适用场景
有 n 个节点，编号为 0 到 n - 1。初始时每个节点各自构成一个连通分量。请实现 UnionFind，支持以下操作：
union(a, b)：合并a和b所在的分量；只有原本不同的两个分量发生合并时才返回
True。
connected(a, b)：判断两个节点当前是否属于同一分量。count()：返回当前连通分量数量。
本题允许 n = 0，但任何操作参数都必须是合法编号，否则抛出 IndexError。基础题只增加连接， 不删除边；调用由单个线程完成。比如 n = 6 时依次合并 (0, 1)、(1, 2)、(3, 4)， 当前有 3 个分量：{0, 1, 2}、{3, 4} 和 {5}。再合并 (2, 4) 后只剩 2 个；此时 union(0, 3) 应返回 False，分量数不能再次减少。
这是通用软件工程编码面试中的数据结构题。核心场景是连接不断加入，同时穿插大量“是否连通”与 “还剩多少组”查询。若所有边一次性给出、只需计算一次连通分量，DFS 或 BFS 往往更直接；这个区别 也属于题目的一部分。
面试官考察点
第一项信号是能否选对状态。并查集不保存完整图，而把每个集合表示成一棵父指针树；根节点代表该 集合，且根的父节点是自己。connected(a, b) 因而可以归结为比较两个根，而不必从头遍历所有边。
第二项信号是合并是否只连接根。直接写 parent[a] = b 可能把一棵树的中间节点改挂到另一节点， 破坏原集合的结构。正确步骤是先求 roota 与 rootb，确认两根不同，再把较小树的根挂到较大树 的根。size 只对根有定义，用它控制树高。
第三项信号是能否解释路径压缩，而非只背模板。本实现采用路径折半：find 向根移动时，让当前节点 改指向祖父节点。新父节点仍在同一棵树中，因此连通关系不变；后续查找路径会变短。路径折半用循环 完成，也避开长路径上的递归深度问题。
最后看计数不变量、复杂度口径和验证意识。components 初始为 n，只在两个不同根合并后减一； 重复合并和自合并都不能改变它。按大小合并与路径压缩同时使用时，单次操作在一串操作上的均摊时间 为 O(α(n))，不是每一次调用都严格 O(1)。
回答前需要澄清的问题
- 连接只增加，还是也会删除？ 只增加时使用标准并查集。任意删除一条边后，剩余边是否仍能让
两点连通无法从父指针森林恢复，需要离线算法或更复杂的动态连通结构。
- 查询是在线穿插，还是所有边一次性给出？ 在线的合并与连通查询适合并查集；静态图只做一次
分量统计时，邻接表加 DFS/BFS 的 O(n + m) 解法更直观，还保留实际边。
union的返回值是什么？ 本题返回是否真的合并。这个布尔值可直接用于环检测，也能保证分量
计数只更新一次。
- 非法节点怎样处理？ 本题抛出
IndexError。如果调用方已经保证编号合法，可以删除检查以缩短
竞赛代码；不能让 Python 的负下标悄悄指向数组尾部。
- 需要查询分量大小或列出成员吗？ 根上的
size可在近似常数均摊时间内回答大小；列出全部成员
仍至少与输出量成正比，并查集本身没有维护成员列表。
- 是否有并发调用？ 基础实现会在
find中写父数组，不是只读操作，也不是线程安全的。若必须
并发，需要定义锁粒度或选择专门的并发并查集算法。
30 秒回答框架
“我用两个长度为 n 的数组：parent[x] 指向父节点，size[root] 记录根所在树的大小；初始每个 节点的父节点是自己，分量数是 n。find 沿父指针找根，并在途中把节点改指向祖父节点做路径 折半。union 先找两根；相同就返回 False，不同则把较小树的根挂到较大树的根，累加大小，把 分量数减一并返回 True。连接两个根不会产生环，路径折半只在原集合内部改父指针，所以连通关系 保持正确。初始化是 O(n)，之后每次操作均摊 O(α(n))，空间是 O(n)。”
分步骤深入解答
最直接的表示法是给每个节点保存一个分量编号。connected 只需比较两个编号，但合并两个分量时 必须扫描整个数组，把旧编号全部改成新编号，单次 union 会达到 O(n)。另一种朴素方案是只用 父指针树，却总把一棵根挂到另一棵根而不控制大小；一串不利合并可形成长链，使 find 退化。
推荐方案维护三项状态：
parent[x]是x的父节点，且每棵树的根满足parent[root] == root。size[root]是该根对应分量的节点数；非根位置的旧值不再读取。components等于父指针森林中的根数量。
实现如下。_validate 很短且只在本类使用，所以保留在使用处，不单独抽成工具模块。
class UnionFind:
def __init__(self, n: int) -> None:
if n < 0:
raise ValueError("n must be non-negative")
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def _validate(self, x: int) -> None:
if x < 0 or x >= len(self.parent):
raise IndexError("node out of range")
def find(self, x: int) -> int:
self._validate(x)
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a: int, b: int) -> bool:
root_a = self.find(a)
root_b = self.find(b)
if root_a == root_b:
return False
if self.size[root_a] < self.size[root_b]:
root_a, root_b = root_b, root_a
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.components -= 1
return True
def connected(self, a: int, b: int) -> bool:
return self.find(a) == self.find(b)
def count(self) -> int:
return self.components正确性可以分三步说明。初始化时每个节点是唯一根，森林包含 n 棵单节点树，三个不变量都成立。 路径折半把 x 的父节点改为原父节点的父节点；祖父仍在同一条通向原根的路径上，所以不会跨集合， 也不会改变 find(x) 的最终根。
合并时只操作两个根。若根相同，两节点已经连通，状态不变。若根不同，把 root_b 指向 root_a 会把两棵树连接成一棵，并且不可能成环，因为两根原本属于不同树；新根大小等于两棵树 大小之和，根数量恰好减少一。由此归纳可知，两个节点连通当且仅当 find 返回同一根，count() 始终等于真实分量数。
按大小合并保证一个节点每次因整棵树被挂到别处而增加深度时，它所在分量的大小至少翻倍；即使不做 路径压缩，树高也至多是 O(log n)。再结合路径折半，一串 m 次查找和合并在初始化之后总计为 O(m α(n)) 的均摊界。α 是反阿克曼函数，增长极慢；面试中可以说“近似常数均摊时间”，但不应 把它改写成严格的最坏 O(1)。两个数组占 O(n) 空间，循环式 find 的额外栈空间是 O(1)。
可以用下面这组操作手算状态：
n = 6 count = 6
union(0, 1) -> True count = 5
union(1, 2) -> True count = 4
union(3, 4) -> True count = 3
connected(0, 2) -> True
connected(0, 4) -> False
union(2, 4) -> True count = 2
union(0, 3) -> False count = 2验证不能只看一条示例。至少覆盖 n = 0 且不调用查询、n = 1 的自合并、重复合并、两个独立 分量再桥接、孤立节点、按相反顺序反复合并，以及 -1 和 n 两个非法编号。对随机小图，还可以 维护一份邻接表，每次加边后用 BFS 计算连通性和分量数，与并查集逐步对照；这是一种很有效的差分 测试。
若所有 m 条边一开始就已知，并且只问一次分量数，建立邻接表后从每个未访问节点做 DFS/BFS， 时间和空间都是 O(n + m)，代码意图也很清楚。并查集的优势出现在边逐条到来、查询与合并交错， 或需要在 Kruskal 算法中快速判断加入无向边是否成环。选择依据是操作模型，不是“看到图就用并查集”。
高质量示范回答
“我先确认关系只会新增，查询会和新增操作交错，并且 union 要返回是否真的合并。这样我会用 并查集；如果只是静态图的一次分量统计，DFS 会更直接。
状态包含 parent、根节点上的 size 和当前根数量 components。初始每个节点指向自己。 find 循环向根移动，每走一步把当前节点改指向祖父，既缩短路径，也避免递归深度问题。union 找到 两根后，如果相同就返回 False，不改计数；否则把较小树的根挂到较大树根上，累加大小并把计数 减一。
这个实现始终是一片森林。路径折半只把节点连向同一树中的祖先；合并只连接两棵不同树的根，所以 不会形成父指针环。每次成功合并恰好把两棵树变成一棵，因此分量数也正确。
构造两个数组需要 O(n)。按大小合并配合路径折半后，查找、连通判断和合并的时间都是 O(α(n)) 均摊，空间是 O(n)。我会重点测试自合并与重复合并不减少计数、桥接两个大分量、孤立 节点、空结构和非法负下标；随机小规模下再用 BFS 作为参照做差分验证。”
常见错误
- 直接设置
parent[a] = b→a可能不是根，原树的一部分被错误拆开或形成难以控制的链
→ 先分别 find，只连接两个根。
- 每次都让第二棵树挂到第一棵树 → 不利顺序会制造长链 → 按根上的
size或rank合并。 find只返回parent[x]→ 父节点未必是根，间接连通会被误判 → 沿父指针走到自指根。- 成功或失败都执行
components -= 1→ 重复合并和自合并会让计数越来越小 → **仅在两根不同
时更新计数。**
- 交换根后仍更新旧变量的大小 →
size与实际树结构分离 → **先确定最终父根，再统一连接和
累加。**
- 声称每次操作最坏
O(1)→ 复杂度保证针对操作序列且含反阿克曼函数 → **报告
O(α(n)) 均摊。**
- 忽略 Python 负下标 →
find(-1)会访问最后一个节点而非报错 → 公共实现显式检查上下界。 - 把并查集用于任意删边 → 父指针没有保存替代路径，无法判断删除后是否断开 → **改用离线删除
处理、回滚并查集或动态连通结构。**
- 把
connected当成只读方法 → 路径折半会写parent，并发调用可能竞争 → **先定义同步契约，
再选择全局锁、分段方案或并发算法。**
追问及应对
追问 1：如何用并查集检测无向图中的环？
逐条处理边 (u, v)。若 union(u, v) 返回 False，两端在加边前已经连通，新边会闭合一个环； 若返回 True，它只是连接两个原本分开的分量。这个规则只直接适用于无向图；有向图的环检测应使用 三色 DFS、拓扑排序等方法。
追问 2：如果要支持撤销最近一次合并呢？
使用回滚并查集：按大小合并，并把每次真实修改前的父节点、根大小和分量数记录到栈中，撤销时恢复。 通常不做路径压缩，因为一次 find 会修改路径上多个位置，导致回滚日志膨胀且边界复杂。只按大小合并 仍把树高限制在 O(log n)，适合配合时间线分治处理离线动态连通。
追问 3：如果关系可以任意删除呢？
标准并查集不能在线回答任意删边。若整段操作提前已知，可以把每条边的有效时间区间放进时间线线段树， 遍历时配合回滚并查集；只在结束时删除的边也可以倒序转成加边。真正在线且高频的插入、删除和查询需要 更复杂的全动态连通数据结构。面试中应先确认操作是否离线，因为这会决定问题等级。
追问 4：怎样返回某个分量的大小或全部成员？
大小已经保存在根上，可以实现 size_of(x) = size[find(x)]，均摊时间不变。列出成员不能只靠根大小； 扫描全部节点并比较根需要 O(n α(n))，额外维护成员集合又会增加合并成本和内存。若需求是偶尔导出， 扫描通常更简单；若每次合并后都要枚举成员，应重新评估数据结构。
追问 5：多个线程并发调用时怎么处理？
最小正确改法是用一把互斥锁包住 find、union 和 connected，因为路径折半会写父数组；这样容易 证明但会串行化全部操作。只有性能测量表明它是瓶颈时，才值得采用基于原子比较交换、确定性挂接顺序 或分区的并发并查集。并发版本必须重新证明父指针无环、大小更新和分量计数的原子性，不能只把数组 换成原子类型。