tarjan 算法疑问
查看原帖
tarjan 算法疑问
542128
liyixin0514楼主2024/11/29 15:55

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

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;
    }
}
2024/11/29 15:55
加载中...