@[Phrvth](/user/520544) 两种写法回溯到 $v$ 时它的 $low$ 相同
by Imiya @ 2023-07-14 18:46:06
@[yuanjiabao](/user/455558) 啊？为啥回溯到v会更新u的low啊？
再说，如果u->v是条横叉边咋办？
by Phrvth @ 2023-07-14 18:56:09
@[Phrvth](/user/520544) 如果 $u$ 有一条返祖边指向 $y$，如果 $low_u$ 是 $dfn_v$ 而不是 $low_v$，在从 $u$ 到 $v$ 的回溯过程中一定不会判出强连通分量，应为遍历完 $low$ 会上传，所以回溯过程中所有点的 $low$ 一定大于等于 $dfn_v$，到了 $v$ 时你 $low_u$ 拿 $low_v$ 或者 $dfn_v$ 更新已经无所谓了。
by Imiya @ 2023-07-14 19:10:44
第一句的 $y$ 改为 $v$
by Imiya @ 2023-07-14 19:11:10
@[Phrvth](/user/520544) 如果 $u$ 到 $v$ 是横叉边意味着 $dfn_v$ 一定小于 $u$ 所在的这个叉的所有点的 $dfn$，所以你拿 $dfn_v$ 更新 $u$ 在这个叉内都不会误判，回溯到 $u,v$ 的公共祖先后它的 $low$ 会对子树内所有点的 $low$ 取 $\min$，所以不影响
by Imiya @ 2023-07-14 19:15:03
@[yuanjiabao](/user/455558) 这样啊，我看下，谢谢你
by Phrvth @ 2023-07-14 19:42:29