并查集#

核心： find(x) 路径压缩找根 / union(x,y) 按秩合并

应用： 连通分量 / Kruskal最小生成树 / 社交网络好友圈 / 岛屿数量

并查集是一种管理不相交集合的数据结构，支持两个核心操作：find查找元素所属集合的根节点，union合并两个集合。朴素实现下find是O(n)的，但两个优化同时用后均摊 O(α(n))（α 是反阿克曼函数，实际不超过 4，可视为常数）：路径压缩——find过程中把沿途所有节点直接指向根，下次查询一步到位；按秩合并——合并时让矮的树挂到高的树下，避免退化成链表。典型应用场景包括：判断图的连通性（两点是否在同一连通分量）、Kruskal最小生成树算法（判断加边是否成环）、社交网络中的好友圈划分、LeetCode岛屿数量的并查集解法。需要注意的是，标准并查集只能合并不能拆分，这是它和BFS/DFS的核心区别——并查集适合动态加边、只合并不拆分的连通性查询，每次查询均摊 O(α(n))，而 BFS/DFS 每次查询要 O(V+E)。

追问方向：

• “路径压缩和按秩合并哪个更重要？”→ 实际中路径压缩提升更明显，但单独使用只能保证均摊 O(logn)；单独按秩合并保证每次最坏 O(logn)（树高 ≤ logn）；两者同时用才是均摊 O(α(n))（Tarjan 证明）
• “并查集能拆分集合吗？”→ 标准并查集只支持合并不支持拆分；若需撤销可用可撤销并查集（只按秩合并、不做路径压缩，用栈回滚最近的 union）或可持久化并查集，删边场景可离线倒序处理，将删边转化为加边
• “什么题型适合并查集？”→ 连通性判断、动态连通分量计数、最小生成树 Kruskal 算法、等价类合并（如账户合并）、判断图中是否有环等

易错点：

• ❌ 并查集可以拆分——标准并查集只能合并不能拆分
• ❌ 并查集和 BFS/DFS 功能一样——并查集只回答「是否连通」，支持在线加边；求具体路径、最短距离仍要 BFS/DFS
• ❌ 只加路径压缩就是 O(α(n))——单独路径压缩是均摊 O(logn)，要和按秩（或按大小）合并一起用