一句话答案

并查集管理不相交集合，路径压缩+按秩合并后 find/union 近似 O(1)，应用于连通性判断和 Kruskal 算法。

核心要点

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

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

追问与易错

追问方向：

• 路径压缩和按秩合并哪个更重要？
• 并查集能拆分集合吗？
• 什么题型适合并查集？

易错点：

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

💡 记忆锚点

并查集像户籍管理：每个人指向自己的"族长"（parent），find就是沿着指针找到族长（路径压缩：找到后直接指向族长，下次O(1)），union就是让两个族的族长认同一个老大（按秩合并：矮树挂到高树下，保持平衡）。判断两人是否同族就看族长是不是同一个。只能合并不能拆分。