寻找桥的判断，if (low[w]>ord[v])的判断。。

Question

这个判断能否改为 if (low[w]> low[v])  ？

Answer 1

liuyubobobo 2019-09-17 02:10:55

不可以。low[v] 表示通过 v 的另一条路（不是dfs树上的路）可以到达的最低 ord 节点。low[w] 则是通过 w 的另一条路（不是dfs树上的路）可以到达的最低 ord 节点。low[v] 和 low[w] 之间不构成关系，和 v-w 是否是桥没关系。

比如下面的例子：

可以测试一下，按照你的咯及，会错误的判断 v-w 是桥，因为 low[w] > low[v]，但是，v-w不是桥。

相应测试图的数据：

4 5
0 1
0 2
1 2
1 3
2 3

继续加油！：）

• 提问者 慕桂英雄 #1

  我是明白了这个low和ord的语义，但是好像举不出反例说服自己。。
  low[w] 一开始会被赋值成和ord[w]一样，随着dfs的遍历，ord[w]不会改变，而low如果能到达祖先节点时可能变小的。
  课上的那几个图，g，g2，g3 我用 if (low[w]> low[v]) 做出来的结果和 if (low[w]>ord[v]) 是一样的。。
  但我知道不对，只是不知道反例是长什么样的。。

• 提问者 慕桂英雄 #2

  其实是上周力扣周赛里有一个找桥的问题，虽然90分钟内没做完，不过后来做的时候发现了这个问题， if (low[w]> low[v]) 可以通过大对数的测试用例，不过有个10000个节点的测试用例没通过。那个图点太多，也不知道长什么样子。。。

• liuyubobobo 回复 提问者 慕桂英雄 #3

  我在原答案上添加了一个反例。

点开查看后面1条评论