并查集（Union-Find）高频题

• find/union 基础操作
• 路径压缩 + 按秩合并
• 只压缩不按秩合并的退化

并查集基础：find(x) 找根（路径压缩），union(a,b) 把两个集合合并（按秩合并）。路径压缩 + 按秩合并使单次操作摊还 O(α(n))（α 为反阿克曼函数，实际 ≤4）。路径压缩把 find 路径上的节点直接指向根，降低下次 find 深度；按秩合并把较小的树挂到较大的树下，控制树高。两者结合保证树高极低，摊还近乎 O(1)。只压缩不按秩合并：不按秩合并时，树可能退化（如一直把大树挂到小树下，或链式合并），树高可能高达 O(n)，某些 find 最坏 O(n)；虽然路径压缩会缓解，但最坏情况下单次 find 仍可能 O(n)（如构造特殊合并顺序使路径压缩难以降低树高）。故两者缺一不可。

O(α(n)) 依赖"路径压缩 + 按秩合并"协同。按秩合并用"秩"控制树高，路径压缩用"扁平化"降低访问深度。只压缩不按秩合并因树高可能失控，最坏退化到 O(n)。掌握"why both"是复杂度证明的关键。

• 并查集加边
• 两端同集合 = 成环
• 冗余边判定

冗余连接：图是 n 个节点的树加一条边，多出的那条边使图成环。用并查集：逐条加边，对每条边 (u,v)，若 find(u)==find(v)（两端已在同一集合），说明 u、v 已连通，此边会形成环，是冗余边，返回它。若不在同一集合，则 union 合并（加入树）。原理：并查集维护"连通分量"，加入一条边前若两端已连通，则这条边必然构成环（必有别的路径连接 u、v），符合"树 + 一条边"的场景，该边即冗余边。按输入顺序遍历，最后一个构成环的边（题目要求返回最后一个）即答案。

关键洞察：并查集在"加边前检查两端是否已连通"——已连通则此边成环，是冗余。这是"动态连通性检测环"的经典应用。树加一条边恰有一个环，并查集能定位构成环的那条边。

• 坐标映射一维下标
• 扫描陆地合并
• 连通分量统计

二维并查集：把网格 (i,j) 映射到一维下标 in+j（n 为列数）。扫描每个格子，若为陆地，则把该格与上下左右相邻的陆地格合并（union）。合并后统计连通分量数：初始每个陆地格是独立集合，每次 union 两个不同集合时分量数减 1。坐标为 (i,j) 的格子的上下左右分别是 (i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)，对应一维下标。映射的关键是"in+j"保证唯一、不越界检查。典型应用：岛屿数量（并查集版本）。

二维并查集把"网格连通分量"转为"一维并查集集合"。映射 i*n+j 是核心，扫描时只合并右/下（或上/下/左/右）相邻陆地避免重复。统计分量数在合并时递减。这是"网格 + 并查集"的通用框架。

• 并查集统计连通分量
• 与 DFS/BFS 对比
• 复杂度

岛屿数量并查集：把每个陆地格映射为一维下标，初始每个陆地格是独立集合（分量数=陆地数），扫描时合并相邻陆地格，每次合并成功分量数减 1，最终分量数即岛屿数。时间 O(m·n·α)，空间 O(m·n)（parent 数组）。与 DFS/BFS 对比：DFS 洪泛 O(m·n) 时间、O(m·n) 最坏栈/队列空间（DFS 递归栈深可达网格大小）；BFS O(m·n) 时间、O(m·n) 队列空间；并查集 O(m·n·α) 时间、O(m·n) 空间。三者时间都线性，空间都 O(m·n)。并查集优势在"动态/增量合并"与"并行"（各区域可独立 union），DFS/BFS 更简单直接。选型：静态计数用 DFS/BFS 最简，需动态或并行用并查集。

三种解法都是"连通分量"视角。DFS/BFS 用遍历洪泛，并查集用合并计数。时间都 O(m·n)，空间 O(m·n)。并查集在"动态合并"与"需 union 语义"的场景更灵活。掌握三者可应对"连通分量"类问题。

• 朋友关系合并
• 连通分量计数
• 邻接矩阵遍历

省份数量：isConnected 矩阵表示城市间的朋友关系，省份是连通的城市集合。用并查集：每个城市初始自成一省（分量数=n），遍历矩阵，若 isConnected[i][j]==1 且 i≠j，则 union(i,j)，若 union 成功（不同集合）分量数减 1。最终分量数即省份数。也可用 DFS/BFS 遍历连通分量，或用"计数根"（统计 find(i)==i 的个数）。并查集合并朋友关系后，分量数 = 独立根数 = 省份数。复杂度 O(n²)（遍历矩阵）。

省份数量是"并查集统计连通分量"的直接应用：矩阵的 1 表示边，合并后分量数即省份。也可用"计数根"（find(i)==i）得到分量数。掌握"合并后数根"是统计连通分量的通用方法。

• 边界 O 的特殊处理
• 虚拟节点合并边界 O
• 只翻转非边界 O

被围绕的区域：把被 X 包围的 O 改为 X，但边界上的 O 及其连通区域不翻转。用并查集：建一个虚拟节点（总节点数），把所有边界上的 O 并入虚拟节点；然后遍历所有 O，若其与虚拟节点连通（说明连通到边界），则保留；否则翻转。原理：先合并边界 O 到虚拟节点，标记"与边界连通"的集合；遍历时，非虚拟集合的 O 都是被包围的（不与边界相连），翻转。这与"从边界 BFS 标记"的思路等价，但用并查集。若没先合并边界 O，直接翻转所有不在"边界连通集合"的会误翻转边界连通的 O。虚拟节点统一了"边界连通"的判定。

虚拟节点是并查集的"统一标记"技巧：把所有边界 O 并入虚拟节点，使"与边界连通"变为"与虚拟节点同集合"。遍历时非虚拟集合的 O 即被包围，翻转。避免误翻的关键是"先标记边界连通再翻转"。

• 邮箱为节点建并查集
• 按邮箱合并账户
• 字典序输出

账户合并：把属于同一人的邮箱合并，按字典序输出。用并查集以邮箱为节点：① 遍历所有账户，建立邮箱→账户名的映射（邮箱属于哪个账户）；② 对同一账户内的邮箱，两两 union（或统一 union 到第一个邮箱）——同一账户的邮箱属于同一人；③ 遍历所有邮箱，把 find 结果相同的邮箱归为一组（映射 根邮箱→邮箱列表）；④ 每组按字典序排序邮箱，并加上账户名输出。关键：邮箱是并查集的节点，账户名绑定到根邮箱。合并后按根分组、排序、输出。

以邮箱为节点的并查集：同一账户的邮箱合并，不同账户共享邮箱则自动合并。用"根邮箱→邮箱列表"分组，排序后输出。这是"实体（邮箱）为节点 + 分组还原"的并查集应用。

• 带权并查集（权值=比值）
• union 时权值更新
• 路径压缩时权值累乘

除法求值：维护 a/b 的比值。带权并查集：每个节点存"到父节点的权值"（weight[x] 表示 x/parent[x] 的比值）。find(x) 时路径压缩要累乘权值：find(x) 递归，先找根，再 weight[x] *= weight[parent[x]]（把 x 到根的新权值算出来），parent[x] 指向根。union(a,b)：已知 a/b=ratio，设 a 的根 ra、b 的根 rb，则 weight[ra] 需满足 a→ra 的比值与 b→rb 的比值以及 a/b=ratio 的关系，即 weight[ra] = ratio * weight[b] / weight[a]（若把 ra 挂到 rb 下）。查询 a/b：若同根，则 a/b = weight[b]/weight[a]（都折算到根）。核心：权值沿路径累乘（find 时）、union 时按比值更新根权值。

带权并查集在 find 时累乘权值（路径压缩），union 时按已知比值推导根权值。查询时用两节点到根的比值相除。这是"并查集 + 比例"的经典题，路径压缩的权值累乘是关键。

• 连通分量数
• 固定 n 台电脑
• 最少缆线数

连通网络的操作次数：n 台电脑、connections 条线，求最少操作数使所有电脑连通。推导：使 n 个节点连通最少需要 n-1 条边（生成树）。若初始有 c 个连通分量（用并查集统计），则最少需要 c-1 条边把各分量连成一棵树。因此最少操作数 = 连通分量数 - 1。前提：线数 ≥ n-1 才可能（否则返回 -1 缆线不足）。用并查集统计可用缆线（未成环的）与连通分量：多余边数 = E - (n - c)（已用的树边），若多余边 ≥ c-1 则可完成，操作数 = c-1。也可直接：若 E < n-1 返回 -1，否则操作数 = 连通分量数 - 1。

核心是"n 个节点连通需 n-1 条边"与"连通分量数 c 需 c-1 条边连接"。并查集统计分量数 c，操作数 = c-1。前提检查缆线是否足够（E ≥ n-1）。这是"并查集 + 树边数"的推导。

• 情侣配对
• 错位环与连通分量
• 最少交换次数

情侣牵手：N 对情侣坐在 2N 个座位（row 数组），每两个相邻座位是一对，求最少交换次数使每对情侣相邻。最少交换次数 = N - 连通分量数。推导：把每对情侣看成节点，若某对情侣的成员被其他情侣"隔开"，则构成"错位"关系。用并查集：对每对相邻座位 (row[2i], row[2i+1])，若它们不是情侣，则把这两个元素所属的情侣对 union（记录"错位连接"）。最终连通分量数 c 表示"错位环"的数量，每个错位环需要 (环长-1) 次交换，总交换 = Σ(环长-1) = N - c。故最少交换次数 = N - 连通分量数。并查集统计错位环的连通分量。

关键是把"情侣配对"转化为"错位环"：每对相邻坐错的人构成一条连接，连接形成环，每环需"环长-1"次交换。并查集统计连通分量 c，交换次数 = N - c。这是"并查集 + 环计数"的经典题。

• 可交换下标并查集
• 分组取字符
• 排序还原

交换字符串中的元素：给定可交换的下标对，求可得到的字典序最小字符串。用并查集：把可交换的下标对 union，同一集合内的下标可任意交换。分组还原：① 遍历所有下标，用并查集分组（根→该组下标集合）；② 对每组，收集该组下标对应的字符，排序后按组内下标升序放回。即可得到字典序最小。原理：同一并查集内的字符可任意重排，排序后放回每个组可达字典序最小。复杂度 O(n log n)（排序每组）。

"可交换的传递性"由并查集捕捉：若 i 可交换 j、j 可交换 k，则三者同集合可任意交换。分组后组内字符排序放回即得字典序最小。这是"并查集 + 分组排序"的题。

• 离线排序查询
• 边按权排序、查询按 limit 排序
• 并查集增量合并

检查边长度限制的路径是否存在：对每个查询 (u,v,limit)，判断是否存在路径使路径上每条边权 < limit。离线套路：① 把边按权从小到大排序；② 把查询按 limit 从小到大排序；③ 用指针遍历查询，对每个查询，把所有权 < limit 的边加入并查集（union），然后判断 u、v 是否连通（find 相同）。正确性：因为边按权递增加入，处理到某查询时，并查集中恰好包含所有权 < 该查询 limit 的边，若 u、v 连通则存在"全边 < limit"的路径。按 limit 递增处理保证"已加入的边"对后续更大 limit 的查询仍然有效（增量），无需重复处理。复杂度 O(E log E + Q log Q + Q α)。

离线排序是"按权增量加边"：边按权升序、查询按 limit 升序，处理查询时并查集恰好含权 < limit 的边。保证正确性靠"增量单调性"——limit 递增时已加入边不失效。这是"离线 + 并查集"的经典套路。

• Kruskal 用并查集检测环
• 按秩合并+路径压缩加速
• 与 Prim 选择依据

Kruskal 用并查集检测环：边按权排序后，逐条考虑，若边两端已在同一集合（会成环）则跳过，否则加入并 union。环检测就是 find 两端是否同根。按秩合并+路径压缩使 find/union 摊还 O(α(n))，把环检测从 O(n)（朴素遍历）降到近乎 O(1)，从而 Kruskal 总复杂度 = 排序 O(E log E) + E 次 find/union O(E α)，总共 O(E log E)。没有路径压缩/按秩合并，find 可能 O(n)，导致 Kruskal 退化。与 Prim 的选择依据：Kruskal 用"边排序 + 并查集"，复杂度 O(E log E)，适合稀疏图（E 小）；Prim 用"堆 + 邻接"，O(E log V)，适合稠密图（E 大）。Kruskal 的并查集是环检测的加速器。

Kruskal 的并查集核心是"O(α) 环检测"，配合路径压缩+按秩合并才能保证整体 O(E log E)。选型：稀疏图 Kruskal（边排序便宜），稠密图 Prim（堆避免全排序）。并查集在 Kruskal 中是"成环检测"的效率关键。

• 三倍扩展域（同类/捕食/被捕）
• 模 3 带权并查集
• 等价性

食物链（A 吃 B、B 吃 C、C 吃 A）：用三倍扩展域并查集——每个动物 x 有三个节点 x、x+n、x+2n，分别表示"x 自身"、"x 吃的东西"、"吃 x 的东西"。关系：同类 = 同一节点的集合；x 吃 y = union(x, y+n) 等。矛盾检测：若说 x 吃 y 但 x 与 y 同类（同集合）则矛盾。模 3 带权并查集：每个节点存到根的权值 mod 3（0 同类、1 被根吃、2 吃根），find 时权值累加 mod 3，union 时按关系更新权值。两者等价：三倍扩展域是空间展开（3 个集合），带权 mod 3 是数值编码（0/1/2 三种关系），都表达"三类关系"（同类/捕食/被捕）。三倍扩展域直观、无模运算，带权 mod 3 空间更省（n 个节点 vs 3n）。两者可达性等价，因关系种类只有 3 种。

种类并查集处理"多类关系"。三倍扩展域用 3×n 个节点显式表达三类身份，带权 mod 3 用权值编码关系。两者数学等价（3 类关系），选型看实现习惯：扩展域直观、带权省空间。理解"关系类型数决定扩展倍数/模数"是关键。

• 小集合并入大集合
• 维护 set 统计
• O(n log n) 复杂度

启发式合并（small-to-large）：合并两个集合（如 set 容器）时，把小集合的元素逐个插入大集合，而非大集合插小集合。这样每个元素每次被合并到至少两倍大的集合，最多被移动 O(log n) 次，总复杂度 O(n log n)。维护统计：合并时同步维护 size、和、最大值等——把小编的元素逐个加入大集，同时更新统计（size+、sum+、max 比较）。应用：并查集按秩合并是同一思想（按树大小 merge），DSU on tree（树上启发式合并）用"重儿子保留、轻儿子合并"。小集入大集保证"每个元素移动次数 O(log n)"，总 O(n log n)。

启发式合并的复杂度关键在于"小入大"的规模倍增：每元素每次移动时所在集合至少翻倍，故移动次数 ≤ log n。这是"集合合并"的 O(n log n) 优化。DSU on tree 是它的树形推广。

• 相似判定（两字符不同）
• 两两枚举合并
• 复杂度 O(n²·L)

相似字符串组：两个字符串相似当且仅当可通过交换两个字符得到（或相同），即恰好两个位置不同。分组：把相似的字符串并入同一组。做法：① 对每对字符串 (i,j) 判断是否相似（统计不同字符数，≤2 则相似）；② 若相似则 union(i,j)；③ 最后统计连通分量数即组数。判断相似：遍历两个字符串的每一位，统计不同位置数，若不同位置数恰好 2（或 0，相同）则相似。复杂度：两两枚举 O(n²) 对，每对判断 O(L)（L 为字符串长度），总 O(n²·L)。

相似字符串组是"两两相似判定 + 并查集合并"。复杂度由"两两枚举 n² × 每对相似判断 L"决定。相似判定是"计数不同位置 ≤2"。这是"并查集 + 两两关系"的题。

• 等价字符并查集
• 每类最小字符
• 替换

按字典序排列最小的等效字符串：给定等价关系（s1、s2 中对应字符等价），把 baseStr 中每个字符替换为它的等价类中最小的字符，得字典序最小。用并查集：把 s1[i]、s2[i] 对应的字符并查集合并（等价字符同集合）。替换：对 baseStr 的每个字符，找其所在集合的根，取该集合中最小字符（等价类最小）。实现：找到根后，遍历 'a'-'z' 找与根同集合的最小字符（或维护每类的 min）。替换后得字典序最小字符串。复杂度 O(n α)。

等价类并查集把"等价字符"分组，替换时取每类字符最小值。关键：并查集合并等价关系，查询时遍历字母表找同类最小。这是"等价类 + 最小替换"的题。

• 二分图无奇环
• 扩展域/带权并查集
• 与染色法对比

判断二分图：图是二分图当且仅当无奇环（可二染色）。并查集判定：用扩展域或带权并查集。扩展域：每个节点 x 分裂为 x 与 x+n（x 的"反色"），对边 (u,v)，union(u, v+n) 与 union(v, u+n)（表示 u 与 v 异色）。若某次 union 时发现 u 与 v 同色（find(u)==find(v)），则矛盾（非二分图）。带权并查集：每个节点存到根的奇偶性（0 同色、1 异色），union 时按边更新权值，find 时权值累加，若出现"同色连接"矛盾则非二分图。原理：奇环会导致"u 与自身异色"的矛盾（绕环权值 mod 2 为 1），故能检测奇环。与染色法对比：染色法 DFS 二染色，遇到相邻同色即非二分图，O(V+E)、直观；并查集法 O(V+E) 但用"合并异色关系"检测矛盾，适合动态加边场景。两者等价。

二分图判定=无奇环。染色法直接二染色，并查集用"异色关系合并 + 矛盾检测"。扩展域/带权并查集都能检测"奇环导致的同色矛盾"。染色法更简单直观，并查集适合动态。掌握两者等价性。

• 在线加边 + 并查集
• 可撤销并查集（按时间撤销）
• 离线场景

在线加边查询连通：只能加边（不能删边）时，用普通并查集即可——每次加边 union，查询是否连通用 find 判断。O(α) 每操作。可撤销并查集：当需要支持"撤销上一次加边"（如按时间回退、离线区间查询）时，普通并查集无法撤销（路径压缩破坏历史）。可撤销并查集用"按秩合并 + 操作栈"：每次 union 记录 (两点, 原秩) 到栈，撤销时按栈逆序恢复（回退秩与父指针）。注意路径压缩会破坏可撤销性，故可撤销并查集关闭路径压缩、仅按秩合并（每次 O(log n)）。离线场景：如"区间加边查询"、时间线分治（CDQ）——把操作按时间分治，递归时加边、回溯时撤销，配合可撤销并查集回答历史查询。

在线加边用普通并查集，可撤销需"按秩合并 + 操作栈"（关闭路径压缩以支持逆序恢复）。离线场景（时间线分治/区间查询）用可撤销并查集在递归中加边与撤销。理解"路径压缩与可撤销冲突"是关键。

• 删除边难、加边易
• 倒序处理删除
• 离线顺序

反向加边：删除边问题（如"删除边后判断连通性"）用并查集难处理（并查集不支持删边），但"加边容易"。技巧：倒序处理——先处理所有删除操作后的最终状态（建出"不包含被删边"的并查集），然后逆序回放：把删除操作反向变成加边操作，每加回一条边更新连通性。离线顺序：① 先读全部操作，标记哪些边会被删除；② 用"从未被删除的边"建初始并查集；③ 逆序处理操作序列：遇到"删除边"时，反向执行"加边"（union）；遇到"查询连通"时，用当前并查集回答。这样把"删除"转为"加边"，正确性由"逆序恢复"保证。典型应用：离线删除边后的连通性查询、Kruskal 重构树。

反向加边是"处理删除问题的离线技巧"：并查集只支持加边，故把删除逆序变加边。核心是"先建最终状态，再逆序回放删除（变加边）"。配合离线顺序保证每次查询时并查集状态正确。