当前位置：首页 > news >正文

对于tarjan的思考

news 2026/5/12 10:55:34

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

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]);}
}

先说结论

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

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

在进行求解时我们最关心的是 $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$ 不是割点。