Tarjan 算法（强连通，割点，桥）对比总结

Tarjan 算法中定义了两个数组：

• $pre_u$: 节点 u 的前序遍历编号
• $low_u = \min\lbrace pre_x | x = u \text{或存在一条从 x 到 u 的子树的反向边} \rbrace$，如果是有向图还要规定$x$在$u$到根节点的路径上，无向图不用这个是因为无向图中的反向边一定指向到根节点路径中的某一个点。
  • 换言之，$low_u$就是$u$的子树中的节点经过最多一条反向边能到达节点的最小$pre$值。

在强连通分量以及点双连通分量算法中，还要在遍历的时候用一个栈维护遍历过的节点，在特定的时候将栈中的某些节点弹出形成所对应的分量。

强连通分量 #

当$pre_u = low_u$时，将$u$以及之后的节点弹出，这些节点属于同一个强连通分量。

割点与点双连通分量 #

割点与点双连通分量个关系：一个割点会属于多个点双连通分量，且两个点双连通分量的交集中最多只有一个点。

当$low_v \ge pre_u$($v$为$u$在 dfs 树中的一个直接儿子) 时，$u$已经之后的节点属于同一个点双连通分量，将$v$以及之后的节点弹出。如果$u$属于至少两个点双连通分量则$u$为割点。

桥与边双连通分量 #

桥与边双连通分量的关系：桥将图分割为边双连通分量，即一条边为桥当且仅当边的两端属于不同的分量。

一条边$(u, v), pre_u < pre_v$为桥当且仅当$low_v > pre_u$。

松弛 low 数组定义 #

在强连通分量以及边双连通分量中，去掉$low$数组中最多一条反向边的限制并不会影响算法的正确性，而且可以简化编码和记忆难度。

假设存在一个点$u$，其两种定义的$low_u$不同，也就是说$low_u$所对应的节点处还有一条反向边，设该反向边的另一节点为$v$。由于$low_u \le pre_u$考虑以下两种情况：

• 情况 1：$low_u = pre_u$，所以我们可以利用$u$的反向边得到更小的$low_u = pre_v$，与$low$的定义矛盾。
• 情况 2：$low_u < pre_u$，松弛定义之后$low_u$依然小于$pre_u$，这并不影响两个算法的判定。

也就是说当且仅当$low_u < pre_u$时，两种定义的$low_u$才会不同。在强连通分量中，这种情况不会影响条件的判定。在边双连通分量中，当$low_v < pre_v$时，$low_v \le pre_u$（因为$u$是$v$到根节点路径上$pre$值最大的节点）所以$(u, v)$边已经是桥了，不会影响判定。然而，在点双连通分量中，当$low_v = pre_u$时，如果$u$处有反向边，松弛定义之后$low_v < pre_u$，使得前后两种判定结果不一致导致算法的正确性无法得到保证。