算法面试题：并查集

1. 什么是并查集？

• 并查集用于维护不相交集合。
• 支持合并（union）和查找（find）操作。

2. 并查集的优化方法有哪些？

• 路径压缩。
• 按秩合并。
• 使用树形结构降低复杂度。

3. 并查集常见应用场景有哪些？

• 连通性问题。
• 网络连接。
• 群组合并。

4. 面试常问的并查集题有哪些？

• 岛屿数量。
• 朋友圈/社交网络连接。
• 最小生成树中的 Kruskal 算法。

5. 并查集的时间复杂度是多少？

• 单次操作摊销近似 O(α(n))。
• α(n) 是极慢增长的反阿克曼函数。

6. 如何判断两个元素是否属于同一集合？

• 通过 find(x) 和 find(y) 是否相同。