对tarjan的一个经典思考

· · 算法·理论

本文章由此文章基础进行思考为什么，以下两份代码可以互换。

for (int i = head[u]; i ; i = G[i].next){
    int v = G[i].v;
    if (!dfn[v]){
        tarjan(v);  //说明v还未在栈中
        low[u] = min(low[u], low[v]);
    }
    else if(!scc[v]){
        low[u] = min(low[u], dfn[v]);
    }
}
}

for (int i = head[u]; i ; i = G[i].next){
    int v = G[i].v;
    if (!dfn[v]){
        tarjan(v);  //说明v还未在栈中
        low[u] = min(low[u], low[v]);
    }
    else if(!scc[v]){//看这里
        low[u] = min(low[u], low[v]);
    }
}

先说结论

  1. 在强连通分量可以写成第二份代码。
  2. 在边双连通分量可以写成第二份代码。
  3. 在点双的时候只能写成第一份代码。

为什么强连通分量可以互换？

在进行求解时我们最关心的是 u 可不可以回到更早入栈的节点，从而形成一个环。

如果 u 到 v 的边是后向边（也称回溯边）并且 v 在栈中那么可以得到 v 是 u 的祖先节点。

如果你在使用的是第二份代码当 low_v < dfn_v 时，但是根据强连通图的传递性，若 u 有到达 v 的路径并且 v 有到达 w 的路径，可以想到 u 和 w 之间肯定也有路径可以到达。

因此根据性质按照第二份代码的 low_u 就有可能会变小但是最终的 u 还有 v 都会被合并到和 w 或者 w 更上层节点为根的强连通分量中。

注意：

虽然经过证明可以互换但是如果要严格符合 low_u 的定义（追溯的节点的 dfn 值），还是建议使用第一份代码。

为什么边双连通分量可以互换？

先回顾怎么判断一条边是否为桥，如果是桥那么必须满足 low_v > dfn_u，在开头引用的文章中已经讲述。

在边双连通分量中我们关心的是边的连通性问题。如果有一条从 x 到 y 的返祖边，那可以理解成 x 和 y 有路径形成了一个环。

若我们认为第二份代码是正确的我们就认为了 x 可以到达 y 能到达的最高点。

因为我们是在无向图中使用边双连通分量而且我们又没有路径可以让一个节点不经过父节点直接到祖先节点形成环。

如果 x 可以通过 y 节点到达更上层的 z 节点也最多只会让构造的环变大，那根据上一段话，能回到比父亲更早的节点就不是桥了，这样写是可以满足的，也不会将桥判定成非桥，将非桥判定成桥。

为什么点双连通分量不可以互换？

假设 u 是割点那么就会存在 u 的子节点 v 使得 low_v \ge dfn_u 成立即可。

先给出反例再给出证明。

反例：

进行第二份代码的模拟，先处理 3 的返祖边，也就是 3 到 1，此时 low_3=dfn_1。接着处理 3 节点的子树 4 和 5。在 5 节点处会有返祖边 5 到 3。按照第二份代码就会有 low_5=\min(low_5,low_3)，此时的 low_5 就会有 low_3 也是 dfn_1 的值，在回溯的时候 low_4 也会变成 dfn_1。

在 3 这个节点判断是否为割点时发现 low_4 < low_3，判断 3 不是割点。

错误原因

算法会认为 4 能绕过 3 直接到达 1 节点但是根据肉眼判断很明显 3 没了 4 就到不了 1，点 3 其实是割点。

正确做法

如果使用第一份代码的写法，对于 5 到 3，只会有 low_5=dfn_3，而 low_4=low_3 满足 3 是割点的条件程序认为 3 是割点，程序正确。

总结

强连通分量具有传递性，只要在同一个强连通块内，值传得更小不影响根的判定。在边双连通分量中，只要能回到父亲节点的上面，该边就不是桥。传递更小的值依然满足点可以回到父亲节点之上的祖先节点。点双连通分量不可以是因为第二份代码的 low_v 会穿过是割点的父节点从而导致错误的继承导致错误的判定。