寻找桥

来源：8-2 寻找桥的算法思路

梦想强大的人i

2021-01-28

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

写回答

1回答

liuyubobobo

2021-01-28

已采纳

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

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

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

继续加油！：）

梦想强大的人i

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

2021-01-29

共1条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1