并查集求无向图连通分量个数
哪些公司问过
答案要点
- 初始化每个节点为独立集合,连通分量计数为 N
- 遍历每条边合并两端点,根不同时合并并让计数减一
- find 用路径压缩,union 用按秩或按大小合并,均摊近似常数
- 求最大连通分量大小时维护 size 数组,合并时累加
- 注意节点编号起点、孤立点、自环和重边等边界
易错点
- 合并时直接 parent[a]=b,没有先找各自的根
- 最后统计根节点时没有再调用 find,误用未压缩的 parent 值
- 把最大连通分量大小和连通分量个数混淆
面试官常见追问
- 不用并查集还能怎么做?
- 路径压缩和按秩合并分别解决什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。