社区讨论

关于Tarjan中low[]的更新条件

学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lztr9asm
此快照首次捕获于
2024/08/14 19:15
2 年前
此快照最后确认于
2024/08/14 21:11
2 年前
查看原帖
Tarjan\text{Tarjan} 算法求强连通分量时,在处理边 (u,v)(u,v) 时,只有当 vv 在记录当前可能强连通分量的栈中时才会用 lowvlow_v 更新 lowulow_u
为什么 vv 在栈中这个条件是必要的?如果 (u,v)(u,v) 是树边且 vv 不在栈中,则说明以 vv 为根的子树自成一个强连通分量,此时有 lowv=dfnv>dfnulow_v=dfn_v>dfn_ulowvlow_v 肯定更新不到 lowulow_u。若 (u,v)(u,v) 是反向边,则 vv 肯定在栈内。
请问诸位大佬我的想法出了什么问题?

回复

2 条回复,欢迎继续交流。

正在加载回复...