【图论】Tarjan 入门

_Weslie_ · 2025-07-16 09:41:04 · 算法·理论

update 2025.8.21：发现几个锅，改一改。

这篇文章是题单 【图论】Tarjan 入门 的配套文章。

注意到 Tarjan 是一个算法，而不是一类问题。事实上有向图用 Tarjan 解决的问题和无向图用 Tarjan 解决的问题是两类不同的问题。我一般称之为“强连通分量问题”和“双连通分量问题”。

有向图的 Tarjan（强连通分量问题）

相比双连通分量问题，强连通分量问题应用更广泛一些。

强连通分量的定义

有向图 G 强连通是指，G 中任意两个结点连通。

例如下面的图就是强连通的：

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

例如：

这张图中，\{7,8,9\} 构成一个强连通分量。另外的两个强连通分量分别是 \{2\} 和 \{1,3,4,5,6\}。虽然 \{1,3,4,5\} 两两之间也可达，但它不是最大的。

我们要运用到 Tarjan 算法。在 OI 中，Tarjan 算法一般是指求强连通分量或双连通分量的算法。

有向图的 dfs 树

这是一个有向图。

我们 dfs 遍历整张图。所经过的边应该是红色的边：

这些红边组成了一颗 dfs 树，这些边统称为树边。

但是还有一些边没有遍历到。

所以我们再定义两类边：

返祖边：顾名思义，从一个点连向其祖先的边叫做返祖边。

这张图中，蓝色的边是返租边：

但还有一些边没有被覆盖到。这些边我们叫做横叉边（下图中的紫色边）。

看图理解：横叉边就是在两个不同的子树里面乱插的边。

辅助数组：dfn 和 low

我们定义两个辅助数组和一个辅助栈。

• 栈用于存储当前仍未进入强连通分量中的节点。

注意：有向图和无向图中 low 的定义不同。

强连通分量的求解

文字描述

我们先来文字版叙述一遍过程：

1. 当前节点 u 入栈，初始化 dfn_u 和 low_u（low_u\leftarrow dfn_u），标记节点入栈

2. 遍历 u 的邻居 v。

   • 如果 v 还没有被遍历过，那么 v 就是 dfs 树中 u 的儿子。遍历一遍，然后根据定义，令 low_u\leftarrow \min(low_u,low_v)。
   • 否则，考虑 v 是否还在栈中。如果还在，则 low_u\leftarrow \min(low_u,dfn_v)。
3. 遍历完邻居后，如果 low_u=dfn_u，说明子树内无法回到 u 以上的点，就将 u 还在栈中的子树分离出来成为一个新的强连通分量（注意标记该节点已不在栈中）。所以用栈——因为子树后遍历先出去，符合栈的特点。

图解

举个例子（点左边蓝色的权值为 dfn，右边红色的权值为 low）：

先遍历前四个点，这都不在话下。这四个点依次入栈。

到 8 的时候，你会发现返租边所连的 1 还在栈中，所以 low_8=1。

向上更新 4 和 3 的 low。这都不在话下。

遍历 9，9 号点再遍历横叉边，得到 low_9=4。

向上回溯到 1，更新 low。这都不在话下。

然后遍历 7。7 连着一条到 5 的横叉边，于是 low_7=2。

继续往下遍历。（实际上 2 是 6 的祖先，但是这里没画好）

现在 low_6=8。向上回溯时发现，low_2=dfn_2（也就是说 2 的子树只能被困在 2 以下了。

于是把 \{2,6,10\} 三个点分出来，变成一个新的强连通分量（出栈）。