Tarjan判断为什么不能把dfn写成low

Tarjan,我相信大多数人是这么写的:

void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    st.push(x),vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int u=to[i];
        if(!dfn[u])
        {
            tarjan(u);
            low[x]=min(low[x],low[u]);
        }else if(vis[u])
            low[x]=min(low[x],dfn[u]);
    }
    //......
}

那么,在else句中,为什么是low[x]=min(low[x],dfn[u])而非low[x]=min(low[x],low[u])呢?

我们来观察这样一个图:

(画图工具画的有点难看)

很明显,③是割点。如果从1开始Tarjan,我们发现,如果用dfn更新,那么1、2、3在同一个强连通分量,即low=1。而4、5的low则是3.这样是正确的。

但如果用low更新的话,4、5的low全部都将更新为1.因为当5查询到3时,若用low更新5的low,5的low就被更新为3的low——1.这显然是错误的。

原文地址:https://www.cnblogs.com/BrotherHood/p/13327910.html