寻找桥

Question

bobo老师，寻找桥是否能用并查集？每条边都可以尝试不放入并查集，如果最后并查集中连通分量个数>1，那么这条边就是桥了。

Answer 1

liuyubobobo 2021-01-28 22:40:25

我没有太理解你的思路。如何，“每条边都可以尝试不放入并查集”，那么边放入并查集的顺序是什么？

如果是尝试 n 轮的话，整个算法是 O(n^2) 的，课程中介绍的算法是 O(n) 的。

Leetcode 的 1192，就是寻找桥。把你的想法写成代码，试试看？https://leetcode-cn.com/problems/critical-connections-in-a-network/

继续加油！：）

• 提问者 梦想强大的人i #1

  思路是对的，不过由于算法时间复杂度是 O(n^2) 的，果然超时了。。