1回答

liuyubobobo

2019-09-17

已采纳

不可以。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

继续加油！：）

5

4

慕桂英雄

非常感谢！这个反例举得好~

2019-09-18

共4条回复