力扣1319:连通网络的操作次数
哪些公司问过
答案要点
- 网线数小于 n − 1 时直接返回 −1
- 网线够用时,答案 = 连通分量数 − 1
- 冗余边(成环的边)足够多是因为总边数 ≥ n − 1
- 并查集统计分量,路径压缩加按秩合并,O(n + E·α(n))
- 也可用 DFS/BFS 遍历邻接表数分量,O(n + E)
易错点
- 先数分量再判断边数,漏掉边数不足返回 −1 的情况
- 误以为答案是冗余边数量,而不是分量数减一
- 递归 DFS 在 n 很大时可能栈溢出,可改用迭代或并查集
面试官常见追问
- 为什么边数够了就一定有足够的冗余边?
- 如果要求输出具体怎么挪线呢?
- 并查集的两个优化各起什么作用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。