桥的小疑问

Question

老师，我看你在判断是否是桥的时候，if条件是 if (low[w] > ord[v])，
但是在上一节的模拟算法里面。我理解的if条件是 if (low[w] > low[v])，
然后我把条件换成我自己理解的，执行结果也对。
但是因为low[v] = Math.min(low[v], low[w]); 所以low[v]的值有被更新。
所以两个if判断条件，应该不是都对的吧。

Answer 1

liuyubobobo 2020-06-24 15:51:09

正确的条件是  if (low[w] > ord[v])

LC 的 1192 号问题就是寻桥算法，你可以尝试一下，使用这个问题，应用你的条件，看能否 AC 这个问题？

中文版链接：https://leetcode-cn.com/problems/critical-connections-in-a-network/

英文版链接：https://leetcode.com/problems/critical-connections-in-a-network/submissions/

继续加油！：）

• 提问者 qq_红_14 #1

  老师，你好。1192号问题，我过会儿做一下。但是单从逻辑上来说，我想不出来if (low[w] > low[v]) 错在哪里。

• liuyubobobo 回复 提问者 qq_红_14 #2

  刚刚测试了一下，写成 low[w] > low[v]，对于课程中的 g3，输出的答案就是错误的（没有桥但是错误地找到了一个桥）。使用这个测试用例调试一下？https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/08-Bridges-and-Cut-Points/04-Bridges-Algorithm/g3.txt

• 提问者 qq_红_14 回复 liuyubobobo #3

  万分感谢老师