亚麻OA难题 Critical Connections in a Network

惊闻本周leetcode周赛出了这题（题号1192）
特来地里发帖希望引起大家注意，此题是近期亚麻OA高频题（我也遇到了）要是碰到了而且没做过，几乎不可能做出来
题意大致是，给定一个connected undirected graph，找出所有“去掉一条边之后会导致整个graph不再是connected”的边
此题|V|,|E|<=10^5，不超时的算法只有一种，而且此前从未在leetcode上出现过，可以看这个链接学习：https://www.geeksforgeeks.org/bridge-in-a-graph/

我用 无向图找环 的算法在里扣上python accepted了，就是用时比较多。

tarjan，这个题确实比较变态，提前没见过肯定过不去，不是能临时想出来的，感谢楼主分享。

labi 发表于 2019-9-17 10:29
我用 无向图找环 的算法在里扣上python accepted了，就是用时比较多。

我用BFS看去掉每个edge是否还能reach到destination。。。timeout.....也是PYTHON。。。心塞。。

william217 发表于 2019/10/08 21:30:50
我用BFS看去掉每个edge是否还能reach到destination。。。timeout.....也是PYTHON。。。心塞。。

当时比赛的时候用无向图找环的算法居然accepted了，但是前几天一摸一样的code就fail了，原来LC加了一个testcase，之前11个，现在12个。
学习了一下tarjan算法，这个貌似是bridge，顺便把找点的cut vertex情况也学习了。

我之前oa也遇到了这道题。。。

感谢分享

刚才OA遇到了这道题，因为之前有看amazon的OA题目所以做过，leetcode上能AC的代码放到OA里就是14/16，关键后面的test case不让看我都不知道哪里错了……感觉没啥问题啊_(:з」∠)_

我也遇到了

我也遇到了，但是和lc的不一样啊，只返回关键点，不是返回一条边，按照lc的做法，没过。。