并查集#

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

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

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

追问方向：

• “路径压缩和按秩合并哪个更重要？”→ 路径压缩对实际性能提升更大，单独使用几乎就能达到接近 O(α(n)) 的均摊复杂度；按秩合并是理论最优的保证，两者结合效果最好
• “并查集能拆分集合吗？”→ 标准并查集只支持合并不支持拆分；若需拆分可用可持久化并查集或离线倒序处理，将删边转化为加边
• “什么题型适合并查集？”→ 连通性判断、动态连通分量计数、最小生成树 Kruskal 算法、等价类合并（如账户合并）、判断图中是否有环等

易错点：

• ❌ 并查集可以拆分——标准并查集只能合并不能拆分
• ❌ 并查集和 BFS/DFS 功能一样——并查集是离线的效率更高