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.这显然是错误的。

巴特西

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

最新文章

热门文章