关于Tarjan中low[]的更新条件
  • 板块学术版
  • 楼主_FILARET_
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/14 19:14
  • 上次更新2024/8/14 21:11:49
查看原帖
关于Tarjan中low[]的更新条件
84121
_FILARET_楼主2024/8/14 19:14

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_u,lowvlow_v 肯定更新不到 lowulow_u。若 (u,v)(u,v) 是反向边,则 vv 肯定在栈内。

请问诸位大佬我的想法出了什么问题?

2024/8/14 19:14
加载中...