这次，我想用尽量简明的语言，来记录一下 Tarjan 算法的学习。
本文篇幅较长，完整阅读大约需要 15-20 分钟。
0x00 Tarjan 算法的用途
当我们接触到一个新的算法的时候，首先要知道它的适用场景。Tarjan 是图论中一个重要的算法。对于无向图，Tarjan 算法能在 $O(n)$ 的时间内，求出无向图的割点与割边，进而求出无向图的双连通分量；对于有向图，Tarjan 算法能够求出有向图的强连通分量、必经点与必经边。
0x01 概念
割点与割边（桥）
给定无向图 $G=(V, E)$：
割点：若对于点 $x \in V$，从 $G$ 中删去 $x$ 及与 $x$ 相连的边之后，$G$ 分成了两个以上不相连的子图，那么 $x$ 称为图 $G$ 的割点。
割边（桥）：若对于边 $e \in E$, 从 $G$ 中删去边 $e$ 后，$G$ 分裂成两个不相连的子图，那么 $e$ 称为图 $G$ 的割边（或桥）。
简而言之，割点与割边可以理解为沟通两张不相连的图，使它们成为一张图的枢纽：
搜索树
在图 $G=(V,E)$ 中，任选顶点 $x$ 作为起点对整张图进行 DFS，每个点只访问一次——此时，每个节点最多有一条入边 $e_{x}$ ，所有在 DFS 过程中经过的边，就构成无向图的搜索树。如果 DFS 的时候遇到了多个分支，我们总是走最左边的那个分支。
时间戳（aka. DFS 序）
节点 $i$ 的时间戳（或 DFS 序）是节点在图的 DFS 中被访问的顺序，也就是说深度优先遍历一张图的时候，$i$ 节点是第 $t$ 个被访问的节点，那么 $i$ 的 DFS 序就是 $t$, 记作 $dfn[i] = t$.
追溯值
追溯值是个比较难理解的东西。在我们对整张图进行 DFS 的过程中，正在访问中的节点会加入一个栈 $s$ 中，节点 $i$ 追溯值的意义是：从节点 $i$ 或其子搜索树中的节点出发，能够追溯到的正在 DFS 栈 $s$ 中的节点序号。而我个人认为比较能理解接受的意义是：从节点 $i$ 出发，除了走通向 $x$ 的父节点 $p$ 的边 $(p, x)$ 之外，能到达的 dfn 最小的节点的序号。
在上图中，考虑节点 2 的追溯值。因为节点 5 可以通过一条不在搜索树上的边到达节点 1，因此 $low[5] = dfn[1] = 1$. 而 5 是 4 的子节点，4 是 3 的子节点……层层向上回溯，最终有 $low[2] = low[3] = low[4] = low[5] = 1.$.
考虑节点 7 的追溯值，因为 7 没有子节点也没有出边，所以 $low[7]$ 只能等于 $dfn[7] = 7$.
考虑节点 6 的追溯值，因为节点 9 可以通过一条不在搜索树上的边到达节点 6，因此 $low[9] = dfn[6] = 6$, 层层回溯最终有 $low[6] = low[8] = low[9] = 6$.
节点 $i$ 的追溯值我们用 $low[i]$ 表示。根据定义，我们计算 $low[i]$ 的方法如下：
- 初始化，首先令 $low[i] = dfn[i]$
- 考虑 $i$ 的每条出边（不包括通向 $i$ 的父节点的出边）$(i, j)$，如果 $j$ 是 $i$ 在搜索树上的子节点，那么 $low[i] = min(low[i], low[j])$
- 如果 $j$ 不是 $i$ 在搜索树上的子节点，也不是 $i$ 的父节点，说明 $j$ 不在搜索树上，那么 $low[i] = min(low[i], dfn[j])$
- $low[i]$ 应该在 DFS 回溯之前计算，确保 $low[j]$ 在 $low[i]$ 前被计算。
（无向图）双连通分量
点双连通图：不存在割点的图；边双连通图：不存在割边（桥）的图。
点双连通分量 (v-DCC, vertex double connected component): 无向连通图的极大点双连通子图。通俗地讲，就是从一个无向图中选出最多的 $n$ 个点，这些点及其连边构成的图不含有割点，删去 $n$ 个点中的任意一个，其它点仍然连通，图不会分割成多张子图。
类似地，定义边双连通分量（e-DCC, edge double connected component）: 无向连通图的极大边双连通子图。通俗地讲，就是从一个无向图中选出最多的 $n$ 个点及在这些点之间连的 $m$ 条边，构成一张新图，这张新图不含有割边，删去 $m$ 条边中的任意一条，其它点仍然连通，图不会分割成多张子图。
v-DCC 和 e-DCC 统称为双连通分量。注意双连通分量的定义是“极大”的。
缩点
e-DCC 的缩点：设无向图 $G$ 中有多个边双连通分量 $G_{e1}, G_{e2}, …, G_{en}$，把每个 e-DCC 视为独立的节点 $i_{1}, i_{2}, …, i_{n}$, 把两个 e-DCC 间的割边 $(x, y)$看做连接两个独立节点的边，这样做之后原来的图会变成一棵树 or 森林（取决于原图连通与否）。这种把 e-DCC 中的多个节点和边收缩成一个节点的方法，叫做缩点。如下图所示。
v-DCC 的缩点：设无向图 $G$ 中有 $p$ 个点双连通分量 $G_{v1}, G_{v2}, …, G_{ep}$，把原来的 $p$ 个 v-DCC 视为独立节点 $i_{1}, i_{2}, …, i_{p}$（如果有点属于多个 v-DCC, 则多个 v-DCC 中都包含该点），在每两个 v-DCC 的公共点部分引入 $t$ 个新节点 $i_{p+1}, i_{p+2}…, i_{p+t} $，这些节点与 v-DCC 间的连边共同构成一棵树。这样称为 v-DCC 的缩点，如下图所示。
流图 (Flow Graph)
对有向图 $G = (V, E)$, 若存在点 $r \in V$, 满足从 $r$ 出发，能够到达 $V$ 中的所有点，那么图 $G$ 是一个流图，$r$ 称为流图的源点.
流图中的边 $(x, y)$ 有四种类型：
- 树枝边，指 $x$ 为 $y$ 的父节点，这是搜索树中的边；
- 前向边，指 $x$ 为 $y$ 的祖先节点；
- 后向边，指 $y$ 为 $x$ 的祖先节点；
- 横叉边，满足 $dfn[y] < dfn[x]$, 如果一条边不属于上述三种情况之一，那么这条边就是横叉边。
如图所示：
强连通分量（有向图）
强连通图：给定一张有向图 $G=(V,E)$, 若对于图中任意两个节点 $x, y$，既存在 $x$ 到 $y$ 的路径，也存在 $y$ 到 $x$ 的路径，则称该图为强连通图。
强连通分量 (SCC, strong connected component)：有向图的极大强连通子图称为强连通分量。
通俗地讲就是从一张有向图中选出最多 $n$ 个点及其连边构成一张新图，这张新图的每两个点都互相可达。根据定义，环一定是一个强连通图。
有向图的必经点与必经边
有向图的必经点：给定有向图 $G=(V,E)$，起点为 $s$，终点为 $t$，若从 $s$ 到 $t$ 的每条路径都必须经过一个点 $x$，那么 $x$ 就是必经点。
有向图的必经边：若从 $s$ 到 $t$ 的每条路径都经过一条边 $(x,y)$，则 $(x,y)$ 称为必经边或有向图的桥。
这两个定义基本上都是字面意思。
0x02 Tarjan 在无向图中的应用
求割边
首先引入割边（桥）的判定法则：
割边判定法则：如果无向边 $(x, y)$ 是桥，当且仅当 x,y 在搜索树上，y 为 x 的子节点，且 $dfn[x] < low[y]$, 即 x 的 DFS 序小于 y 的追溯值。
证明：根据上面的定义 $low[i]$ 表示由 $i$ 及其子树的节点出发能到达的 $dfn$ 最小的点，如果 $dfn[x] < low[y]$，则说明从点 $y$ 出发，不经过边 $(x, y)$ 无法到达点 $x$ 或比 $x$ 更早访问的节点，此时的图一定分成了两个或以上的部分。
因为搜索树涵盖了每个节点，所以割边（桥）一定是搜索树的边。如果不是的话，那么存在一条不在搜索树上的边 $(x, t)$ 和在搜索树上的边 $(x, y)$ 同时连通两部分，所以割边不可能不在搜索树上。此外，如果有节点相互成环，那么割边也不在环上，因为无论去掉哪条边，环所属的各个点仍然连通。
求出所有的割边，我们可以按照上面的思路，首先计算每个节点的 dfn 和 low 值，然后遍历每个节点 $i$，对于 $i$ 的每条出边 $(i, j)$ 判断，若 $dfn[i] < low[j]$ 则找到了割边。
int cnt = 0; // dfs 序计数
// tarjan 的主算法，本质是一个 dfs 函数，x 是 dfs 的起点
// in_edge 是入边的编号，如果没有入边则编号 0
void tarjan(int x, int in_edge) {
dfn[x] = low[x] = ++cnt; // 初始化
// 遍历 x 的每条出边
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (!dfn[v]) { // 点 y 未被访问
tarjan(v, i);
low[x] = std::min(low[x], low[y]);
// 割边判定法则
if (low[y] > dfn[x]) {
printf("find bridge: %d, %d\n", e[i].u, e[i].v);
}
}
// (in_edge) ^ 1 表示与入边对应的无向边，如果 i 也不是对边对应的无向边那就不在搜索树中
else if (i != (in_edge ^ 1)) {
low[x] = std::min(low[x], dfn[y]);
}
}
}
// 对每个未访问的点执行主算法
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, 0);
求割点
割点的判定法则如下，与割边的大同小异：
若 $x$ 是搜索树的根节点，则 $x$ 是割点当且仅当 $x$ 有 2 个或以上的子节点。
若 $x$ 不是搜索树的根节点，则 $x$ 是割点，当且仅当搜索树上存在 $x$ 的一个子节点 $y$, 满足 $dfn[x] \leq low[y]$。
证明：若 $x$ 是根节点，显然删掉 $x$ 后，$x$ 的子树分别成独立的图；若 $x$ 不是根节点且满足上述条件，说明从 $y$ 出发无法到达比 $x$ 更早被访问的节点（但是能访问到 $x$，鉴于 $x$ 会被删除，因此访问了也没有关系）。
求割点仍然是先计算每个节点的 dfn 和 low 值，然后遍历每个节点 $i$，若 $i$ 是根节点则判断 $i$ 的子节点数；若不是则对于 $i$ 的每条出边 $(i, j)$ 判断 $dfn[i] \leq low[j]$ 即可。
int cnt = 0, root = 0;
void tarjan(int x) {
dfn[x] = low[x] = ++cnt;
int child_count = 0;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
if (low[y] >= dfn[x]) {
child_count++;
if (x != root || child_count > 1)
printf("find cut point %d\n", x);
}
} else {
low[x] = std::min(low[x], dfn[y]);
}
}
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
root = i, tarjan(i);
求无向图的双连通分量
有关于双连通分量的定义，我们在前面探讨过了。接下来我们分别从求 v-DCC 和求 e-DCC 入手。
求无向图的点双连通分量 v-DCC
首先引入判定一张无向图是否为点双连通图的法则。无向连通图是点双连通图时，当且仅当该图满足以下两个条件之一：
- 图的顶点数不超过 2，即 $n \leq 2$；
- 图中任意两点同时包含在至少一个简单环（指不自交的环，就是起点终点都是自己的环）中。
例如，在上面的图中，我们有四组点双连通分量，分别是 1,2,3,4,5 / 1,6 / 6,7 / 6,7,8. 在这些点双连通分量中，任选其中一个点出发，一定能够到达分量中的其它任意一点。
求无向图的点双连通分量，我们需要额外维护一个栈。按照以下的流程来维护栈中的元素：
- 循环遍历每一个节点，若发现某个节点的 $dfn[i]$ 未被计算，则以该点为入口执行 Tarjan 算法；
- 当一个节点第一次被访问的时候，将该节点入栈；
- 遍历节点 $x$ 的每条出边 $(x, y)$，判断 $x$ 是否为割点，即 $dfn[x] \leq low[y]$ 是否成立；
- 若 $x$ 为割点，则从栈顶不断弹出节点，直到节点 $y$ 被弹出或栈为空；弹出的所有节点与 $x$ 共同构成一个 v-DCC.
比如说，在上面的图中，容易看出割点为 1, 6. 我们不妨以 1 为起点开始执行 Tarjan，1->2->3->4->5，栈中元素为 5,4,3,2,1；然后回溯到 1 时，发现有 $dfn[1] \leq low[2]$，说明 1 是割点。那么此时弹出栈中的元素直到 2 被弹出为止，弹出 5,4,3,2，最后 1 也是 v-DCC 的一部分，将其加入；然后搜索 6，6 往下搜索 7 / 8,9 又分别得到两个新的 v-DCC；最后回溯到点 1 时，发现 $dfn[1] \leq low[6]$，1-6 构成一个双连通分量。那么直接把 6 取出，与 1 一起得到一个新的 v-DCC. 这样我们就找到了全部的四个 v-DCC.
另外需要额外注意处理一下一个点单独孤立的情况，此时这个点自身形成一个 v-DCC. 最后，汇合起来代码如下：
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
const int MAXN = 100000;
struct Edge {
int u, v, next;
} e[MAXN << 1];
int head[MAXN], cnt = 1, n, m;
int dfn[MAXN], low[MAXN], dcnt = 0, root = 0;
bool cut[MAXN]; // 记录点 i 是不是割点，这个待会会用到
int ans = 0;
std::stack<int> s;
std::vector<int> dcc[MAXN];
void addEdge(int u, int v) {
e[cnt] = (Edge) {u, v, head[u]};
head[u] = cnt;
cnt++;
}
void tarjan(int x) {
dfn[x] = low[x] = dcnt++;
s.push(x);
if (x == root && head[x] == -1) { // 孤立点，单独成图
dcc[ans++].push_back(x);
return;
}
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
if (low[y] >= dfn[x]) { // x 是割点
cut[x] = 1;
int tmp;
do {
tmp = s.top();
s.pop();
dcc[ans].push_back(tmp);
} while (tmp != y);
dcc[ans].push_back(x);
ans++;
}
} else {
low[x] = std::min(low[x], dfn[y]);
}
}
}
int main() {
memset(e, -1, sizeof e);
scanf("%d%d", &n, &m);
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
root = i;
tarjan(i);
}
}
for (int i = 0; i < ans; i++) {
printf("v-DCC #%d\n", i);
for (int j = 0; j < dcc[i].size(); j++)
printf("%d ", dcc[i][j]);
printf("\n");
}
return 0;
}
测试数据：
9 11
1 2
2 3
3 4
4 5
2 5
1 5
1 6
6 7
6 8
8 9
6 9
求无向图的 e-DCC
求无向图的边双连通分量就比较简单，首先我们使用 Tarjan 算法标记处所有的桥，然后对整个无向图进行一次 DFS，对于节点 $x$ 的出边 $(x, y)$，如果它是割边，则跳过这条边不沿着它往下走；这样我们可以划分出多个连通块，连通块的数目及其包括的节点，就是我们所求的 e-DCC 的数量和包含的节点。
以上面的图为例，图中应该有 2 条割边 (1, 6) 和 (6, 7)，因此有 3 个边双连通分量，如图所示：
我们设置一个新的变量 $c[i]$ 来表示节点 $i$ 所属的 $e-DCC$ 的编号。可以发现，删去割边后，我们在一次 DFS 中访问到的节点都在同一个 e-DCC 中，所以具有相同的 $c[i]$ 值。代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 100000;
struct Edge {
int u, v, next;
} e[MAXN << 1];
int head[MAXN], cnt = 2, n, m; // 为了进行异或运算找到边，必须设定前向星 cnt 起点为 2
int dfn[MAXN], low[MAXN], dcnt = 0;
int c[MAXN], dcc = 0;
bool is_bridge[MAXN];
void addEdge(int u, int v) {
e[cnt] = (Edge) {u, v, head[u]};
head[u] = cnt;
cnt++;
}
void tarjan(int x, int in_edge) {
dfn[x] = low[x] = dcnt++;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (!dfn[y]) {
tarjan(y, i);
low[x] = std::min(low[x], low[y]);
if (low[y] > dfn[x]) { // x 是割边
printf("edge (%d, %d) is bridge.\n", x, y);
is_bridge[i] = is_bridge[i ^ 1] = 1; // 标记该边及其反向边为桥
}
} else if (i != (in_edge ^ 1)) {
low[x] = std::min(low[x], dfn[y]);
}
}
}
void dfs(int x) {
c[x] = dcc;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
// 节点 y 已被访问或者 (x,y) 是桥
if (c[y] || is_bridge[i])
continue;
dfs(y);
}
}
int main() {
memset(e, -1, sizeof e);
scanf("%d%d", &n, &m);
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i, 0);
}
}
for (int i = 1; i <= n; i++) {
if (!c[i]) {
dcc++;
dfs(i);
}
}
printf("There are %d e-DCCs.\n", dcc);
for (int i = 1; i <= n; i++) {
printf("node %d belongs to e-dcc %d\n" , i, c[i]);
}
return 0;
}
e-DCC 的缩点
对无向图的边双连通分量进行缩点很简单，因为我们上面已经求出了每个点所属的 e-DCC, 因此我们只需要遍历每条边 $(x, y)$，如果这条边所连的点 $x, y$ 有 $c[x] = c[y]$，说明他们属于同一个 e-DCC，不需要做任何事情；否则，说明 $(x, y)$ 是割边，将 x, y 加入一张新的图中。完成后新的图就是我们想要的缩完点之后的树或森林。
下面是 e-DCC 缩点的代码，配合上面求 e-DCC 的代码食用。
Edge ec[MAXN << 1];
int hc[MAXN], cecnt = 2;
void add_cut_edge(int u, int v) {
ec[cecnt] = (Edge) {u, v, hc[u]};
hc[u] = cecnt++;
}
for (int i = 2; i <= cnt; i++) { // cnt 是原图的边数
int x = e[i].x, y = e[i].y;
if (c[x] == c[y])
continue; // x, y 同属一个 e-DCC, 无事可做
add_cut_edge(x, y); // 否则将 x, y 加入新树中
}
printf("finish point reducing operation, new tree/forest has %d nodes and %d edges: \n", dcc, cecnt / 2); // 除 2 是因为有重边
for (int i = 2; i < cecnt; i += 2)
printf("%d %d\n", e[i].u, e[i].v);
v-DCC 的缩点
v-DCC 的缩点由于引入了新的关联节点，因此就显得比较复杂。在求完 v-DCC 的基础上，我们的操作步骤是这样的：
- 给每个割点一个新的编号，从 ans+1 开始，ans 表示 v-DCC 的个数。
- 建立一张新的图，加入每个 v-DCC 和该 v-DCC 所包含的所有割点的连边。
大家可以对照着 0x01 的定义部分，模拟一下上面的步骤。下面是代码，熟读并背诵即可：
// 给割点编号
int new_id[MAXN], num = ans;
for (int i = 1; i <= n; i++)
if (cut[i])
new_id[i] = ++num;
// 建立新图
Edge ec[MAXN << 1];
int hc[MAXN], cdcnt = 2;
void add_vdcc_edge(int u, int v) {
ec[cdcnt] = (Edge) {u, v, hc[u]};
hc[u] = cdcnt++;
}
for (int i = 0; i < ans; i++) { // ans 是 v-DCC 数 -1
for (int j = 0; j < dcc[i].size(); j++) {
int x = dcc[i][j];
if (cut[x]) {
add_vdcc_edge(i, new_id[x]);
add_vdcc_edge(new_id[x]. i);
} else {
c[x] = i; // 除了割点之外，标记其它的点只属于一个 v-DCC
}
}
}
printf("finish point reducing operation, new tree/forest has %d nodes and %d edges: \n", ans, cdcnt / 2); // 除 2 是因为有重边
for (int i = 2; i < tc; i += 2) {
printf("%d %d\n", e[i].u, e[i].v);
}
0x03 Tarjan 在有向图中的应用
求有向图的强连通分量
在定义一节中我们提到，一个环一定是一个强连通图。因此，Tarjan 算法求解有向图的强连通分量的基本思路，就是对于每个节点 $i$，尽量找到能与它一起成环的所有节点；找到这些节点之后自然就找到了一张原图的极大连通子图，也就是强连通分量 SCC.
刚刚我们提到，一张流图中有四种边，分别为“树枝边”、“前向边”、“后向边”和“横叉边”。现在我们考虑搜索树上的节点加上这些边如何能成环。根据刚才的定义，后向边是由搜索树中的子节点指向祖先节点的边，因此后向边连通的两个点及两个点在 DFS 中经过的节点一定构成环。而横叉边比较特殊，如果存在一条横叉边 $(x,y)$，满足从 $y$ 出发能找到一条路径回到 $x$ 的祖先节点，那么 $(x, y)$ 就是有用的。
接下来就是，如何利用这两类边去找环。我们需要维护一个栈，当 Tarjan 主算法进行 DFS 到节点 $x$ 的时候，栈中需要保存两类节点：第一类是 $anc(x)$，即 $x$ 在搜索树上的祖先节点的集合；第二类是节点 $i$ 满足 $vis[i] = 1$ 且 $\exists e_{ij}$ 使 $e_{ij}$ 连接 $i$ 和 $anc(x)$ 中的一点（也就是说已访问过、并且存在一条路径到达 $anc(x)$ 集合元素的节点）。我们分别说说存这两类节点有什么意义。
首先是维护 $anc(x)$ 的意义，设 $y$ 是 $x$ 的一个祖先节点即 $y \in anc(x)$, 如果存在后向边 $(x, y)$，则 $y$ 到 $x$ 的路径与边 $(x, y)$ 共同成环。其次是维护已访问过可达 $anc(x)$ 的点的意义，主要用于处理横叉边，如果有节点 $z$ 满足从 $z$ 出发存在一条路径可以到达 $y \in anc(x)$, 那么如果存在横叉边 $(x,z)$，则 $z \to y$, $y \to x$ 和边 $(x, z)$ 成环。
同样的，我们在有向图的 Tarjan 中也存在追溯值的概念。基本计算方法和无向图的追溯值方法是大同小异的，因为引入了边的方向，所以我们在 DFS 和回溯计算的时候需要特别注意：
- $dfn$ 与 $low$ 的初始化，与无向图中求追溯值相同，令 $dfn[x] = low[x] = ++order$.
- 扫描 $x$ 的每条出边 $(x,y)$，如果 $y$ 是搜索树上的节点（$(x, y)$ 是树枝边），那么 $y$ 就没有被访问过，计算完 $low[y], dfn[y]$ 回溯时令 $low[x] = min(low[x], low[y])$.
- 如果 $y$ 不是搜索树上的节点，那么 $y$ 一定被访问过，此时 $(x, y)$ 是后向边，令 $low[x] = min(low[x], dfn[y])$.
- 从 $x$ 回溯之前判断是否有 $low[x] = dfn[x]$ 成立，如果是的话将栈顶元素弹出直到 $x$ 出栈为止。
可以发现，有向图的 Tarjan 算法相比无向图，在判断 $(x,y)$ 是否为搜索树上的边时，用的是指向的结点是否在栈中的判断法；并且有向图在计算完 $low[x]$ 之后，还需要根据条件 $low[x] = dfn[x]$ 是否成立，将栈顶元素弹出，防止后面的 DFS 过程中误将其它分支的节点当做祖先节点。
以前文的有向图为例计算追溯值，特别注意圈出来的几个节点：因为节点 $5$ 存在通向祖先节点 $2$ 的节点，所以 $low[5] = dfn[2] = 2$，再层层回溯，得到 $low[2] = low[3] = low[4] = low[5] = 2$. 最后在回溯到 $2$ 的时候，发现 $dfn[2] = low[2]$ 成立，那么弹出栈中的元素 $5,4,3,2$.
$6-8-9$ 的搜索也同理。
注意节点 $7$，虽然它有一条指向 $4$ 的横叉边，但是搜索到 $7$ 的时候，$4$ 已经不在栈中了，说明这条横叉边并没有什么存在的意义。注意我们之前说过，横叉边 $(x, y)$，只有从 $y$ 能找到一条通往 $x$ 及其祖先节点的路径，这条边才有用。
说了这么多，我们还没有说到用 Tarjan 到底怎么求有向图的强连通分量。其实很简单，在上面的图中我们发现，四个强连通分量是 2,3,4,5 / 6,8,9 / 7 / 1；而这两个强连通分量都是计算追溯值的第四步中，从栈里弹出来的节点。也就是说我们得到了 Tarjan 算法中强连通分量的判定法则：
在追溯值的计算过程中，若从 $x$ 回溯前，有 $low[x] = dfn[x]$ 即 $x$ 的追溯值=DFS序，那么在栈中，从 $x$到栈顶的所有节点构成一个强连通分量。
注意我在判定法则前加了一个定语“Tarjan 算法中”，说明这个法则只有在 Tarjan 算法的特定场景下有意义。上述法则的合理性在于，如果 $dfn[x] = low[x]$，说明子节点可以到达 $x$, 但并不能到达比 $x$ 更早被 DFS 的节点，自然不会和更先前的点成环。
模板代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using std::stack;
using std::vector;
const int MAXN = 100000;
struct Edge {
int u, v, next;
} e[MAXN << 1];
int head[MAXN], cnt = 1;
int dfn[MAXN], low[MAXN], order = 1;
int c[MAXN]; // 缩点的时候会用到，表示节点 i 所属的 scc 编号
int n, m, scccnt = 0;
bool instack[MAXN];
vector<int> scc[MAXN];
stack<int> s;
void addEdge(int u, int v) {
e[cnt] = (Edge){ u, v, head[u] };
head[u] = cnt++;
}
void tarjan(int x) {
dfn[x] = low[x] = order++;
s.push(x);
instack[x] = 1;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
} else if (instack[y]) {
low[x] = std::min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) {
int tmp;
do {
tmp = s.top();
c[tmp] = scccnt;
instack[tmp] = 0;
s.pop();
scc[scccnt].push_back(tmp);
} while (tmp != x);
scccnt++;
}
}
int main() {
scanf("%d%d", &n, &m);
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
addEdge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
printf("Find %d SCC(s.\n", scccnt);
for (int i = 0; i < scccnt; i++) {
printf("SCC #%d: ", i);
for (int j = 0; j < scc[i].size(); j++)
printf("%d ", scc[i][j]);
printf("\n");
}
return 0;
}
测试数据：
9 13
1 2
2 3
3 4
4 5
5 2
1 5
1 6
6 7
7 4
8 7
6 8
8 9
9 6
SCC 的缩点
SCC 的缩点和 e-DCC 的缩点比较类似，不过最后得到的应该是一张 DAG(有向无环图)。上面我们用 $c[i]$ 记录了节点 $i$ 所属的 SCC 的编号，我们对原图的每条边 $(x,y)$ 遍历判断，若 $c[x] \neq c[y]$，就在编号为 $c[x]$ 与 $c[y]$ 的 SCC 之间连边。
Edge ec[MAXN];
int hc[MAXN], ccnt = 1;
void add_scc_edge(int u, int v) {
ec[ccnt] = (Edge) { u, v, hc[u] };
hc[u] = ccnt++;
}
for (int x = 1; x <= n; x++) {
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (c[x] == c[y])
continue;
add_scc_edge(c[x], c[y]);
}
}
0x04 One More Thing - Kosaraju
到上面为止 Tarjan 算法就讲的差不多了。不知道读者有什么感想，我第一次看这些东西的时候满脑子的 WTF，说好要用简明的语言复述一遍，这样下来我已经混乱了。因为 Tarjan 实在是太复杂了（虽然理解之后，代码量是很小的），这里还是要再讲一种稍微简单些的，用来求有向图的强连通分量的算法——Kosaraju 算法。
Kosaraju 算法也可以在线性时间内求出有向图的强连通分量。虽然 Kosaraju 的时间也是线性的，但是因为 Kosaraju 的算法步骤需要对图进行两次遍历，而 Tarjan 算法只需要遍历一次图中的节点，因此实际运用中 Kosaraju 的效率是要略低于 Tarjan 的，但是 Kosaraju 的原理比 Tarjan 简单的呢。有多简单呢？我们来看一张有向图：
在上图中，如果不计单点自己组成的强连通分量，那么很明显有两个强连通的子图：1,2,3 / 5,6,7. 现在我们对这张有向图的边取反（就是把原来的边方向反过来），得到图$G_r$：
此时，我们任选 $G_r$ 中的一个节点为起点，利用深度优先搜索求出 $G_r$ 的逆后序。什么是逆后序呢？我们的 DFS 节点顺序分为前序、后序、逆后序三种，取决于节点在何时被加入什么样的数据结构中，一般我们定义：
前序：在递归调用下一级 DFS 函数之前，将当前节点加入队列
后序：在递归调用下一级 DFS 完成回溯之后，将当前节点加入队列
逆后序：在递归调用下一级 DFS 完成回溯之后，将当前节点加入栈
因此，以 $5$ 为 DFS 起点对 $G_r$ 求逆后序，入栈顺序是：6 7 1 2 3 4 5，而逆后序是从栈顶到栈底的顺序，则逆后序是 5 4 3 2 1 7 6.
接下来，我们按照得到的逆后序，再对原图进行一次 DFS：在同一个 DFS 递归子程序中访问的点，一定是同属一个连通分量的，例如对上面的图，如下图所解释：
这样就求出有向图的强连通分量啦。让我们来理一遍主算法的思路：
- 对于有向图 $G$, 将其每条边取逆 ($(x, y) \to (y, x)$)，得到一张新图 $G_r$，这是 $G$ 的反向图；
- 建立一个栈 $s$, 遍历图 $G_r$ 所有的节点，进行 DFS 求逆后序，并标记已访问的节点；
- 按照 $s$ 栈顶到栈底的节点顺序，对 $G$ 再进行一次 DFS，同一个 DFS 递归子程序中访问的点同属一个 SCC.
代码如下，我实在很难找到网上有的 Kosaraju 的算法 C++ 版本，所以自己撸了一个：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using std::stack;
using std::vector;
const int MAXN = 100000;
struct Edge {
int u, v, next;
} e[MAXN << 1], rev[MAXN << 1];
int head[MAXN], head_rev[MAXN], cnt = 1, scccnt = 0;
int n, m;
bool vis[MAXN];
vector<int> scc[MAXN];
stack<int> reverse_postorder, s2;
void addEdge(int u, int v) {
e[cnt] = (Edge){ u, v, head[u] };
head[u] = cnt++;
}
void reverse_graph() {
for (int i = 1; i < cnt; i++) {
rev[i] = (Edge){ e[i].v, e[i].u, head_rev[e[i].v] };
head_rev[e[i].v] = i;
}
}
void dfs_reverse_postorder(int x) {
vis[x] = 1;
for (int i = head_rev[x]; i; i = rev[i].next) {
if (!vis[rev[i].v]) {
dfs_reverse_postorder(rev[i].v);
}
}
reverse_postorder.push(x);
}
void dfs(int x, bool root) {
vis[x] = 1;
s2.push(x);
for (int i = head[x]; i; i = e[i].next) {
if (!vis[e[i].v]) {
vis[e[i].v] = 1;
dfs(e[i].v, false);
}
}
if (root && !s2.empty() && s2.size() >= 2) {
while (!s2.empty()) {
scc[scccnt].push_back(s2.top());
s2.pop();
}
scccnt++;
} else if (root) {
s2.pop();
}
}
int main() {
scanf("%d%d", &n, &m);
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
addEdge(u, v);
}
reverse_graph();
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs_reverse_postorder(i);
}
}
memset(vis, 0, sizeof vis);
while (!reverse_postorder.empty()) {
int s = reverse_postorder.top();
reverse_postorder.pop();
if (!vis[s])
dfs(s, 1);
}
printf("Find %d SCC(s).\n", scccnt);
for (int i = 0; i < scccnt; i++) {
printf("SCC #%d: ", i);
for (int j = 0; j < scc[i].size(); j++) {
printf("%d ", scc[i][j]);
}
printf("\n");
}
return 0;
}
0x05 Reference
部分内容和代码参考李煜东的《算法竞赛进阶指南》，在此特别感谢。