tarjan 算法疑问

如下是 tarjan 求强连通分量的代码，其中 else 部分 low[u]=min(low[u],dfn[v]); 写成 low[u]=min(low[u],low[v]); 也可以过。请问这两种写法都正确吗？蒟蒻刚学图论 1ms，能否解释一下语句的含义？

CPP

void tarjan(int u) {
    dfn[u]=low[u]=++dfn0;
    st[++top]=u;
    for(int v : to[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!num[v]) {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]) {
        num[u]=++cnt, scc[cnt].push_back(u);
        while(st[top]!=u) scc[cnt].push_back(st[top]), num[st[top]]=cnt, --top;
        --top;
    }
}

讨论操作

回复

相关推荐

tarjan 算法疑问