tarjan求scc疑问
  • 板块学术版
  • 楼主chenwenmo
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/3 11:13
  • 上次更新2024/10/3 14:34:35
查看原帖
tarjan求scc疑问
815504
chenwenmo楼主2024/10/3 11:13
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    sk.push(u);
    for(int v : e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(!num[v]){
            low[u] = min(low[u], low[v]);
            //here
        }
    }
    if(low[u] == dfn[u]){
        num[u] = ++cnt;
        scc[cnt].push_back(u);
        while(sk.top() != u){
            num[sk.top()] = cnt;
            scc[cnt].push_back(sk.top());
            sk.pop();
        }
        sk.pop();
    }
}

代码中 here 那里,虽然说这里的 low 和正常的 low 定义不一样,但如果这么写正确性会受影响吗,如果受影响是因为什么原因呢

2024/10/3 11:13
加载中...