求无向图(含三角网格)的所有连通分量
哪些公司问过
华为1游卡游戏1
答案要点
- 把点视为节点、连接关系视为无向边,连通分量是极大连通子图
- DFS/BFS:建邻接表,未访问点作为起点遍历,一次遍历收集一个分量
- 并查集:按边 union,最后按 find 的根分组,根的数量即分量数
- 孤立点也是独立分量;复杂度约 O(n+m)
- 三角网格需先明确连通定义(共享顶点还是共享边),再建图
易错点
- 漏掉没有任何边的孤立点
- 有向图和无向图混淆,建邻接表时只加了单向边
- 大规模数据下递归 DFS 栈溢出
- 未与面试官确认三角网格连通是按共享边还是共享顶点
面试官常见追问
- 并查集的路径压缩和按秩合并分别做什么?
- 如果边是动态不断加入的,怎么实时维护分量个数?
- 三角网格怎么高效建立三角形之间的邻接关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。