并查集
并查集（Union-Find，又称不相交集合 / Disjoint Set Union，DSU）是一种专门管理一组不相交集合的树型数据结构——它只做两件事：查找（find）某元素属于哪个集合（找根/代表元）、合并（union）两个集合。结构极简（只需一个 parent 数组），却能在路径压缩 + 按秩/按大小合并两大优化加持下，把每次操作的均摊复杂度压到 O(α(n))（α 是阿克曼反函数，对任意可想象的实际 n 都 ≤ 4），近乎 O(1)。它是解决等价类、连通性、动态连通问题的首选利器。
并查集的全部考点都源于一个核心思想：用一棵树表示一个集合，树根就是集合的「代表元」。由此衍生出三大主题：①朴素实现与退化问题（最坏退化成链表，find/union 变 O(n)）；②两大优化（路径压缩让树变扁平、按秩/按大小合并让矮树挂高树，二者结合达 O(α(n))）；③工程应用（连通分量计数、Kruskal 最小生成树的判环、朋友圈/岛屿等价类合并、动态连通性查询、无向图判环与冗余连接）。它本质是把「判断两个元素是否属于同一类」这一高频问题，从每次 O(n) 扫描降到近乎 O(1)——用最少的代码换取最大的性能。
评价
优点
- 近乎 O(1) 的操作：路径压缩 + 按秩合并后，find/union 均摊 O(α(n))，对 n ≤ 10⁸⁰ 都 < 5，实际就是常数——这是并查集区别于其它结构的杀手锏
- 实现极简：只需一个
parent数组（加可选的rank/size），几十行代码搞定，常数因子小，工程上几乎不会写错 - 动态连通性友好：支持「边加边查」，不需要预先知道全部连通关系，适合动态/在线场景
- 承载面广：连通分量、最小生成树（Kruskal）、等价类合并、判环、离线最近公共祖先（Tarjan）都以它为核心
缺点
- 只支持合并，不支持拆分：并查集是「只合不分」的结构，把两个集合拆开很难（需要可撤销并查集或回滚并查集）——这是它最大的硬伤
- 只能判连通，不能查路径：能告诉你 A 和 B 是否连通，但给不出 A 到 B 的具体路径（要路径得用 BFS/DFS）
- 不支持边权/最短路：本质是等价关系维护，处理不了带权最短路径问题（加权并查集能处理相对关系，但仍非通用最短路）
本叶地图
- 入门 —— 不相交集合概念、parent 数组表示、find 找代表元、union 合并两集合、初始每元素自成一组、连通性问题引入
- 路径压缩与按秩合并 —— 朴素 find 的 O(n) 退化树问题、路径压缩（find 时挂根）、按秩合并（矮挂高）、按大小合并（小挂大）、均摊 O(α(n))≈O(1)
- 工程应用 —— 连通分量计数、Kruskal 最小生成树判环、朋友圈/岛屿等价类、动态连通性、无向图判环与冗余连接
- 参考 —— 并查集 API 速查、复杂度表、find/union 代码模板、路径压缩+按秩合并完整实现、应用清单、易错点
交互演示
- 并查集可视化演示 —— parent 数组、路径压缩与按秩合并的动态过程