冗余连接 II(LC685,并查集)
哪些公司问过
答案要点
- 多余边可能导致入度为 2、成环,或两者兼有
- 先找入度为 2 的节点,记录指向它的两条候选边
- 跳过后出现的候选边做并查集,无环则删它,有环则删先出现的那条
- 无入度为 2 的节点时,并查集中造成成环的边即答案
- 并查集带路径压缩,整体近似 O(n)
易错点
- 把有向图当无向图处理,只做环检测
- 有入度为 2 时没有跳过候选边就直接做并查集
- 题目要求返回最后出现的满足条件的边,选错先后顺序
面试官常见追问
- 和冗余连接 I(LC684)有什么区别?
- 为什么跳过候选二后仍有环就该删候选一?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。