在同一个边双连通分量中点low值必定相同?
  • 板块学术版
  • 楼主y_kx_b
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/1/8 10:20
  • 上次更新2023/10/24 05:12:25
查看原帖
在同一个边双连通分量中点low值必定相同?
592895
y_kx_b楼主2023/1/8 10:20

貌似很多地方都是这么认为的(“有多少low值就有多少个边双连通分量”),可我代码跑出了反例。

9 6
7 5
1 2
6 7
4 9
2 4
2 6
5 4

在该无向图中(箭头表示树边,根节点为 1) low[5]=3,low[4]=2 但显然 5 和 4 在同一边双({2,4,5,6,7,9})中。

啊所以请问标题这个结论是否是错误的。

另外,“low值相同的点必定在同一个边双连通分量中”好像是对的。

2023/1/8 10:20
加载中...