关于边双连通分量算法。
  • 板块学术版
  • 楼主ivnilkkk
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/19 21:22
  • 上次更新2025/1/19 21:23:13
查看原帖
关于边双连通分量算法。
1073341
ivnilkkk楼主2025/1/19 21:22

建立好无向 dfs 树后,找桥。

如何求桥?首先,桥一定是树边。对于一条树边 (a,b)(a,b),其中 bbaa 的孩子。如果 low[b]>dfn[a]low[b]>dfn[a],则 (a,b)(a,b) 为桥。

为啥 low[b]>dfn[a]low[b]>dfn[a] 那么 (a,b)(a,b) 就为桥?

2025/1/19 21:22
加载中...