一、为什么要重新谈论“并查集”

• 图数据库的连通分量计算，用并查集能把 O(m×n) 的广度搜索降到近乎线性；
• 图像分割中，把像素当节点，色差当边，并查集可把百万像素聚类成数百区域；
• 编译器做名字合并、操作系统做内存段合并、网络协议做分片重组，背后都是“合并+查询”逻辑；
• 甚至前端状态管理里，也能用并查集维护“模块依赖图”的即时连通性。

二、直觉：连通性问题的“森林模型”

• 节点 = 元素
• 边 = 合并操作
• 根 = 集合标识
  没有复杂的指针，也没有递归栈，只有“父数组”这一张表。把森林映射到数组，是并查集高效的第一步。

三、模板：路径压缩与按秩合并的“双翼”

1. 路径压缩
   在查询过程中，把沿途节点的父指针直接指向根。下一次查询同样路径时，只需一次跳转。均摊分析可知，路径压缩让查询操作接近常数时间。
2. 按秩合并
   每次合并时，让“较矮”的树成为“较高”树的子树，从而控制树高。树高不超过 log n，保证最坏情况下查询仍是 O(log n)。
   双翼齐飞，均摊复杂度降至近乎线性：m 次操作的总代价为 O(m α(n))，其中 α 是反阿克曼函数，在宇宙规模内小于 5。
3. 初始化策略
   父数组初始值可设为 -1，既表示“自己是根”，又能在负数位存储秩（或大小）。这种“负秩技巧”减少一张额外数组，也减少缓存 miss。
4. 迭代式查询
   用循环而不用递归，避免栈溢出；同时在循环里完成路径压缩，一次遍历即可完成“找根+压缩”。

四、进阶：权值、尺寸、反向指针的“增强”

1. 带权并查集
   在父指针之外再存一条“到根的权值”，用于维护“相对差”。典型应用：判断图中是否存在奇环、计算变量间线性关系。路径压缩时，同时更新权值和。
2. 按尺寸合并
   用负数存子树尺寸，合并时小尺寸并入大尺寸，可减少树高；也能用来回答“集合大小”查询。
3. 反向指针
   在“图分割”场景，需要快速枚举“某个集合的所有节点”。可在根处维护一个动态数组，合并时把较小数组拼到较大数组，均摊 O(1)。
4. 懒惰删除
   并不真正删除节点，而是把“删除标记”记录在权值里；查询时若发现路径上存在删除标记，可返回“无效”。适用于“在线加边+离线删边”的动态图。

五、实战：七道经典场景从头到尾“手算”一遍

1. 最小生成树 Kruskal
   按边权排序，依次加边，若两端已连通则跳过。并查集负责“连通性”查询，总复杂度 O(m log m + m α(n))。
2. 省份连通
   给定矩阵，判断几个省份。把邻接关系喂入并查集，最后数根即可。路径压缩后，常数极小。
3. 图着色等价类
   把“颜色相同”的节点合并，最后统计集合数，就是“最少颜料数”。权值并查集可维护“颜色差”。
4. 奇环检测
   带权并查集维护“到根距离的奇偶性”。若加边后两端奇偶性相同，则出现奇环。
5. 并查集树 LCA
   离线 Tarjan 算法用并查集维护“已访问节点集合”，在回溯阶段回答 LCA 查询，复杂度 O(n + q)。
6. 图像区域合并
   像素当节点，色差当边，按边权升序合并，直到“区域数”达到阈值。得到的分割结果比固定阈值扫描更自然。
7. 语法分析中的等价类
   在编译器前端，把“相同的符号表条目”合并，用于名字解析、常量合并、重复类型消除。并查集让“合并+查询”近乎常数，前端解析速度肉眼可见提升。

六、加速：批量合并、SIMD、并发与无锁

1. 批量合并
   事先排序所有边，按根分组，一次性把“同一父节点”的子节点批量指向新根，减少随机写；缓存友好，速度提升 30% 以上。
2. SIMD 加速
   在超级计算机里，把 256 个父指针放进 SIMD 寄存器，一次向量比较完成 256 个查询；适合“超大规模图”的连通分量初筛。
3. 并发并查集
   读多写少场景，用原子变量存储父指针，查询无锁，合并加锁；或采用“版本号”策略，实现无锁合并。论文表明，并发并查集能把“图构建”阶段加速到核心数线性。
4. GPU 并行
   在 CUDA 里，每个 warp 负责一块图；合并时使用“根编号最小”策略，通过 warp shuffle 完成广播；适合“千万节点、亿级边”的连通分量初筛。

七、变形：分层并查集、可持久化并查集、超图并查集

1. 分层并查集
   把节点按深度分层，每层维护一个并查集；用于“动态图加边+删除边”场景，删除时只需分裂上层，无需重建整张图。
2. 可持久化并查集
   每次合并都复制一份父数组，老版本只读，新版本写入；用于“离线询问+回退历史”场景，内存开销 O(m log n)。
3. 超图并查集
   一条超边连接多个节点，合并时把超边所有端点指向同一根；用于“聚类一堆点”的图像分割、社区检测。实现时用“代表元”技巧，把超边映射到“最小序号端点”，避免 N 次合并。
4. 加权并查集森林
   给每条边一个权重，合并时按“权重和”排序；用于“最优子结构”问题，例如“最小权连通子图”。

八、误区与解毒剂

1. “并查集一定最快”
   对于“完全图”，边数接近 N²，并查集常数虽低，但仍跑不过“邻接矩阵+DFS”的特化实现；应根据图密度选择算法。
2. “路径压缩会打乱顺序”
   路径压缩只改变指针，不改变节点值；若业务依赖“子树顺序”，需额外维护列表，而不能仅靠父指针。
3. “递归一定溢出”
   并查集查询用循环实现，但“按秩合并”比较树高时，若用递归，也可能栈溢出；始终用循环比较秩。
4. “并发并查集无锁一定快”
   无锁实现会增加大量 CAS 操作，CPU 缓存行抖动；在竞争不激烈时，简单加锁反而更快。量化后再上并发。

九、调试与可视化：让“森林”看得见

1. 父数组打印
   把父数组按“树高”分层打印，一眼看出哪棵树过高；调试路径压缩时，对比前后两张图，验证压缩效果。
2. Graphviz 导出
   把每棵树的边导出为 dot 格式，生成 PNG；图像化后能快速发现“合并错误”或“环未被检测”。
3. 单元测试数据
   构造“链、星、完全图”三种极端数据，验证“查询路径长度”与“树高”是否符合预期；性能回归用“随机图+计时”即可。
4. 性能基线
   记录“百万节点、千万边”的耗时与内存峰值；后续优化必须给出对比数据，防止“为了炫技而炫技”。