tarjan 算法疑问

B3609 [图论与代数结构 701] 强连通分量

liyixin0514 @ 2024-11-29 15:55:16

如下是 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;
    }
}

by liyixin0514 @ 2024-11-29 16:00:22

如果说根据 OI Wiki，low_u 表示在 u 的子树中能够回溯到的最早的已经在栈中的结点，那么从含义上感觉后者符合。但是 Wiki 上写的是前者。我该如何理解？

by Ask_sum @ 2024-11-29 16:12:42

如果是有向图求 SCC 的话，那这两句都是对的，但是别的连通性问题用 tarjan 只有第一句是对的，最好是都写第一句。

by chaeminter2467 @ 2024-11-29 16:15:20

@liyixin0514 在求强连通分量中两种写法都是正确的，原因是最后这些点都会缩成一个大点，也就是它们的low是一致的。而在使用Tarjan求其他的东西的时候应该注意使用dfn[v]。

我个人认为，low[i]指的就是通过非生成树树边回溯到的最高级的祖先，因为Tarjan的底层其实是使用了生成树的逻辑。

可以去看一下tarjan求点双连通分量和边双连通分量的板子，可以帮助理解。

有歧义的地方欢迎询问 qwq

by GalenoJiao @ 2024-11-29 16:16:45

@liyixin0514 我们老师说的是写成 low[v] 和 dfn[v] 都可以，写成哪种都不影响正确性。

从含义上看 low[v] 是正确的，但是写成 dfn[v] 就可以和双连通分量（特别是点双）的写法保持一致。

by chaeminter2467 @ 2024-11-29 16:17:25

边双 可以看看这个！!!

by chlchl @ 2024-11-29 16:22:00

@liyixin0514 根据定义来说，low_u 是指 u 及其子树通过一条非树边能够回溯到的在栈中最早的点，else 的时候 u\rightarrow v 显然不是一条树边，不能用 low_v（因为 low_v 有可能是 v 又经过了一条非树边才能到达的）。

by liyixin0514 @ 2024-11-29 16:29:53

大概理解了，谢谢各位大佬/bx

by guoguo160 @ 2024-12-13 23:24:48

%%%%%%

|