面试题库 › 客户端 › 冗余连接 II(LC685,并查集)

冗余连接 II(LC685,并查集)

难度 ★★★在 1 场真实面经中被问到 方向:客户端考点:图论

哪些公司问过

腾讯1

常见岗位:C++ / Qt 客户端

答案要点

  1. 多余边可能导致入度为 2、成环,或两者兼有
  2. 先找入度为 2 的节点,记录指向它的两条候选边
  3. 跳过后出现的候选边做并查集,无环则删它,有环则删先出现的那条
  4. 无入度为 2 的节点时,并查集中造成成环的边即答案
  5. 并查集带路径压缩,整体近似 O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题