Tarjan\text{Tarjan}Tarjan 算法求强连通分量时,在处理边 (u,v)(u,v)(u,v) 时,只有当 vvv 在记录当前可能强连通分量的栈中时才会用 lowvlow_vlowv 更新 lowulow_ulowu。
为什么 vvv 在栈中这个条件是必要的?如果 (u,v)(u,v)(u,v) 是树边且 vvv 不在栈中,则说明以 vvv 为根的子树自成一个强连通分量,此时有 lowv=dfnv>dfnulow_v=dfn_v>dfn_ulowv=dfnv>dfnu,lowvlow_vlowv 肯定更新不到 lowulow_ulowu。若 (u,v)(u,v)(u,v) 是反向边,则 vvv 肯定在栈内。
请问诸位大佬我的想法出了什么问题?