有向图的强连通分量

#定义

• 强连通的定义是：对于一个有向图 $G$ 中任意一对节点 $u$ 和 $v$ 可以互相到达。
• 强连通分量的定义是：极大强连通子图。

在上面的定义中，我们称一个强连通子图 $G' = (V', E')$「极大」（其中 $V' \in V, E' \in E$），是指不存在包含 $G'$ 的更大的子图 $G'' = (V'', E'')$，满足 $V' \subseteq V'' \subseteq V, E' \subseteq E'' \subseteq E$，并且 $G''$ 也是强连通子图。

#DFS 生成树

在介绍 Tarjan 算法之前，需要先了解一下 DFS 生成树。

给定一个有向图 $G = (V, E)$，若存在 $r \in V$，满足从 $r$ 出发能够到达 $V$ 中的所有点，则称 $G$ 是一个流图（Flow Graph），记为 $(G, r)$，其中 $r$ 称为流图 $G$ 的源点。

在一个流图 $(G, r)$ 上从 $r$ 出发进行深度优先遍历，每个点只访问一次。所有发生递归的边 $x \to y$ 构成一棵以 $r$ 为根的树，我们称它为流图 $(G, r)$ 的 DFS 生成树。

有向图的 DFS 生成树有四种边，以下面这个有向图为例：

• 树枝边：示意图中以黑色边表示（如 $2 \to 3$），它是在搜索时访问到了一个还没有访问过的节点时形成的。
• 前向边：示意图中以绿色边表示（如 $3 \to 6$），它是在搜索时遇到子树中的节点的时候形成的。
• 后向边：示意图中以红色边表示（如 $7 \to 1$），它是在搜索时遇到祖先节点时形成的。
• 横叉边：示意图中以蓝色边表示（如 $9 \to 7$），它是在搜索时遇到了一个已经访问过的且不是当前节点的祖先的结点时形成的。

不同书籍介绍的这四种边的名称可能不同，但定义内容基本上是一样的。

此外，在 DFS 过程中，按照每个节点第一次被访问的时间顺序，依次给流图中 $n$ 个节点 $1 ~ n$ 的整数标记，该标记被称为 DFS 序（也被称为时间戳），记作 $\text{dfn}$。上图中节点的圆圈内的数字便是该节点的 DFS 序。

#Tarjan 算法

Tarjan 发明了许多算法。本文中的「Tarjan 算法」指的是由 Tarjan 发明的在有向图中强连通分量的算法。

提示：请勿混淆 边 与 路径 的概念。

#实现

一个环一定是强连通图。如果图中既存在从 $x$ 到 $y$ 的路径（不仅仅是边），又存在从 $y$ 到 $x$ 的边，那么 $x, y$ 显然在一个环中。因此，Tarjan 算法的基本思路就是对于每个点，尽量找到与它一起能够构成环的所有节点。

容易发现，从 $x$ 到 $y$ 的前向边并没有什么用处，因为 DFS 生成树上本来就存在从 $x$ 到 $y$ 的路径。从 $x$ 到 $y$ 的后向边非常有用，因为它可以和 DFS 生成树上从 $y$ 到 $x$ 的路径一起构成环。从 $x$ 到 $y$ 的横向边需要视情况而定，如果从 $y$ 出发能找到一条路径回到 $x$ 的祖先节点，那么这条边也是有用的，可以成为环的一部分。

为了找到通过后向边和横叉边构成的环，Tarjan 算法需要在 DFS 的同时维护一个栈。当访问到节点 $x$ 时，栈中需要保存以下两类节点：

1. DFS 生成树上 $x$ 的祖先节点，记为集合 $A(x)$。
   设 $y \in A(x)$，若存在后向边 $x \to y$，则 $x \to y$ 与从 $y$ 到 $x$ 的路径一起形成环。
2. 已经访问过，并且存在一条路径能够到达 $A(x)$ 中的节点。
   设节点 $z$ 符合该要求，从 $z$ 出发存在一条路径能到达 $y \in A(x)$，若存在横叉边 $x \to z$，则这条边和从 $z$ 到 $y$ 的路径还有从 $y$ 到 $x$ 的路径可以共同形成一个环。

综上所述，栈中的节点就是能与从 $x$ 出发的后向边和横叉边形成环的节点。

#追溯值

设 $S(x)$ 表示流图的 DFS 生成树中以 $x$ 为根的子树。$x$ 的追溯值 $low_x$ 定义为满足以下条件的节点的最小时间戳。

1. 该点在栈中。
2. 存在一条从 $S(x)$ 中出发的有向边以该点为终点。

根据定义，Tarjan 算法按照以下步骤计算追溯值：

1. 当节点 $x$ 第一次被访问时，将 $x$ 入栈，初始化 $\text{low}_x = \text{dfn}_x$。
2. 扫描从 $x$ 出发的每一条边 $x \to y$。
   1. 若 $y$ 从未被访问过，则说明 $x \to y$ 是树枝边，递归访问 $y$，从 $y$ 回溯后，令 $\text{low}_x = \min(\text{low}_x, \text{low}_y)$。
   2. 若 $y$ 被访问过且 $y$ 在栈中，则令 $\text{low}_x = \min(\text{low}_x, \text{dfn}_y)$。
3. 在 $x$ 回溯之前，判断是否有 $\text{low}_x = \text{dfn}_x$ 成立。若成立，则不断从栈中弹出节点，直至 $x$ 出栈。

#判定强连通分量

在追溯值的计算过程中，若从 $x$ 回溯前有 $\text{low}_x = \text{dfn}_x$ 成立，则栈中从 $x$ 到栈顶的所有节点均在同一个强连通分量中。

此处不作证明，有兴趣的读者可以自行查找相关论文与书籍。

#实现

说明请见代码注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int cnt,      // 搜索过的节点个数
    dfn[N],   // 每个点的 DFS 序
    low[N];   // 每个点的追溯值
int scc_cnt,  // 强连通分量个数
    id[N],    // 每个点对应的强连通分量编号
    siz[N];   // 每个强连通分量的节点数
bool vis[N];  // 节点是否在栈内
std::stack<int> st;

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    st.push(u);
    vis[u] = true;
    for (int v : g[u]) {
        if (!dfn[v]) {        // 未被访问过
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (vis[v]) {  // 被访问过且在栈中
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;        // 强连通分量的个数加一
        int v;
        do {
            v = st.top();
            st.pop();        // 出栈
            vis[v] = false;  // 取消标记
            siz[scc_cnt]++;  // 当前强连通分量的大小加一
        } while (v != u);    // 循环到节点 x
    }
}

#例题及代码

对应题目：洛谷 - P3387 【模板】缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

// Limits
const int N = 10005;

int n, m, u, v, a[N];
std::vector<int> g[N], g2[N];

// Tarjan
int cnt, dfn[N], low[N];
int scc_cnt, id[N];
int w[N];
bool vis[N];
std::stack<int> st;

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = true;
    st.push(u);
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_cnt++;
        int v;
        do {
            v = st.top();
            st.pop();
            vis[v] = false;
            id[v] = scc_cnt;
            w[scc_cnt] += a[v];
        } while (v != u);
    }
}

// Shortest Path
int dist[N];
int spfa(int s) {
    memset(dist, -0x3f, sizeof(dist));
    std::queue<int> q;
    q.push(s);
    dist[s] = 0;
    int res = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res = std::max(res, dist[u] + w[u]);
        for (int v : g2[u]) {
            if (dist[v] < dist[u] + w[u]) {
                dist[v] = dist[u] + w[u];
                q.push(v);
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int v : g[i]) {
            if (id[i] != id[v]) {
                g2[id[i]].push_back(id[v]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        ans = std::max(ans, spfa(i));
    }
    cout << ans << endl;
    return 0;
}

#参考资料

1. 22.5 强连通分量，《算法导论》中译本（ISBN 978-7-111-40701-0，机械工业出版社），2013 年 1 月第三版。
2. 0x67 Tarjan 算法与有向图连接性，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
3. 连通：有向图，图论：相关概念，OI Wiki，2021 年 8 月 23 日。
4. 强连通分量，图论，OI Wiki，2021 年 11 月 8 日。
5. 3.7 有向图的强连通分量，AcWing 算法提高课，闫学灿，2019 年 11 月 30 日。

本文图片由 OI Wiki 提供，在此对图片作者表示感谢。