求助 tarjan 算法的小细节
  • 板块学术版
  • 楼主Brilliant11001
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/6/14 16:21
  • 上次更新2024/6/14 20:19:47
查看原帖
求助 tarjan 算法的小细节
602372
Brilliant11001楼主2024/6/14 16:21

这是我一直在用的 tarjan 模板:

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u, st[u] = true;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(st[j]) low[u] = min(low[u], dfn[j]); //
    }
    if(dfn[u] == low[u]) {
        int y;
        scc_cnt++;
        do {
            y = stk[top--], st[y] = false;
            id[y] = scc_cnt;
        }while(y != u);
    }
}

请问双斜线的地方一定要写成 dfn[j]dfn[j] 吗?但是刚刚试了试改成 low[j]low[j] 也能过题,写成 low[j]low[j] 逻辑上感觉也没问题。

有没有 dalao 告诉蒟蒻究竟那种写法是正确的并解释原因?

2024/6/14 16:21
加载中...