本课时有配套视频讲解，购买后即可观看（永久有效）
强连通分量
一、课上练习
编程练习
- 强连通分量：L49991
二、知识总结
✨ 核心思想
在有向图中，如果两个顶点 u 和 v 之间可以互相到达（既存在 u→v 的路径，也存在 v→u 的路径），则称 u 和 v 是强连通的。一个极大的强连通子图称为强连通分量（Strongly Connected Component，SCC）。
求 SCC 有两种经典算法：Tarjan 算法和 Kosaraju 算法。Tarjan 算法通过一次 DFS 完成，Kosaraju 算法需要两次 DFS 但思路更直观。
✨ 算法原理
Tarjan 算法
Tarjan 算法在 DFS 过程中维护一个栈，将当前路径上的节点压入栈中。当发现某个节点 u 满足 dfn[u] == low[u] 时，说明 u 是某个 SCC 的"根"（最早被访问的节点），此时将栈中 u 及其上方的所有节点弹出，它们构成一个 SCC。
关键点：
- 节点入栈后，只有在确认属于某个 SCC 时才出栈。
low[u]只能通过栈中的节点来更新（避免跨 SCC 更新）。- 用
in_stack数组标记节点是否在栈中。
Kosaraju 算法
Kosaraju 算法基于一个重要性质：图 G 和其反图 G^T 具有相同的 SCC。
- 对原图 G 做 DFS，按照完成时间（后序）将节点压入栈。
- 构建反图 G^T。
- 按栈中顺序（完成时间降序）对反图做 DFS，每次 DFS 到达的所有节点构成一个 SCC。
✨ 代码实现
Tarjan 算法
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5vector<int> adj[MAXN]; // 有向图邻接表
6int dfn[MAXN], low[MAXN]; // 时间戳与最小可达时间戳
7int scc_id[MAXN]; // 每个节点所属 SCC 的编号
8int scc_cnt = 0; // SCC 总数
9int timer_cnt = 0;
10bool in_stack[MAXN]; // 是否在栈中
11stack<int> stk; // Tarjan 栈
12int n, m;
13
14void tarjan(int u) {
15 dfn[u] = low[u] = ++timer_cnt;
16 stk.push(u);
17 in_stack[u] = true;
18
19 for (int v : adj[u]) {
20 if (!dfn[v]) {
21 // 树边：递归后更新
22 tarjan(v);
23 low[u] = min(low[u], low[v]);
24 } else if (in_stack[v]) {
25 // 指向栈中节点的边（同一 SCC 内的边或返祖边）
26 low[u] = min(low[u], dfn[v]);
27 }
28 // 如果 v 不在栈中且已访问，说明 v 属于已确定的其他 SCC，忽略
29 }
30
31 // 如果 u 是 SCC 的根
32 if (dfn[u] == low[u]) {
33 scc_cnt++;
34 int v;
35 do {
36 v = stk.top();
37 stk.pop();
38 in_stack[v] = false;
39 scc_id[v] = scc_cnt; // 标记所属 SCC
40 } while (v != u);
41 }
42}
43
44int main() {
45 ios::sync_with_stdio(false);
46 cin.tie(nullptr);
47
48 cin >> n >> m;
49 for (int i = 0; i < m; i++) {
50 int u, v;
51 cin >> u >> v;
52 adj[u].push_back(v); // 有向边 u → v
53 }
54
55 for (int i = 1; i <= n; i++) {
56 if (!dfn[i]) tarjan(i);
57 }
58
59 // 输出每个节点所属的 SCC
60 cout << "共 " << scc_cnt << " 个强连通分量\n";
61 for (int i = 1; i <= n; i++) {
62 cout << "节点 " << i << " 属于 SCC " << scc_id[i] << "\n";
63 }
64
65 return 0;
66}Kosaraju 算法
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5vector<int> adj[MAXN]; // 原图
6vector<int> radj[MAXN]; // 反图
7int scc_id[MAXN];
8bool vis[MAXN];
9int scc_cnt = 0;
10int n, m;
11vector<int> order; // 后序遍历顺序
12
13// 第一次 DFS：记录后序
14void dfs1(int u) {
15 vis[u] = true;
16 for (int v : adj[u]) {
17 if (!vis[v]) dfs1(v);
18 }
19 order.push_back(u); // 后序压入
20}
21
22// 第二次 DFS：在反图上标记 SCC
23void dfs2(int u, int id) {
24 scc_id[u] = id;
25 for (int v : radj[u]) {
26 if (!scc_id[v]) dfs2(v, id);
27 }
28}
29
30int main() {
31 ios::sync_with_stdio(false);
32 cin.tie(nullptr);
33
34 cin >> n >> m;
35 for (int i = 0; i < m; i++) {
36 int u, v;
37 cin >> u >> v;
38 adj[u].push_back(v);
39 radj[v].push_back(u); // 反图
40 }
41
42 // 第一步：对原图 DFS，记录后序
43 for (int i = 1; i <= n; i++) {
44 if (!vis[i]) dfs1(i);
45 }
46
47 // 第二步：按后序逆序，对反图 DFS
48 for (int i = n - 1; i >= 0; i--) {
49 int u = order[i];
50 if (!scc_id[u]) {
51 scc_cnt++;
52 dfs2(u, scc_cnt);
53 }
54 }
55
56 cout << "共 " << scc_cnt << " 个强连通分量\n";
57 return 0;
58}✨ 执行示例
以下有向图为例（4 个节点）：
边：1→2, 2→3, 3→1, 3→4
Tarjan 算法过程：
| 步骤 | 节点 | dfn | low | 栈 | 说明 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | [1] | 入栈 |
| 2 | 2 | 2 | 2 | [1,2] | 树边 1→2 |
| 3 | 3 | 3 | 3 | [1,2,3] | 树边 2→3 |
| 4 | - | - | 1 | [1,2,3] | 3→1 是返祖边，low[3]=1 |
| 5 | 4 | 4 | 4 | [1,2,3,4] | 树边 3→4 |
| 回溯 | 4 | 4 | 4 | [1,2,3] | dfn[4]==low[4]，弹出 {4}，SCC#1 |
| 回溯 | 3 | 3 | 1 | [1,2,3] | low[3]=1 |
| 回溯 | 2 | 2 | 1 | [1,2,3] | low[2]=min(2,1)=1 |
| 回溯 | 1 | 1 | 1 | [] | dfn[1]==low[1]，弹出 {3,2,1}，SCC#2 |
结果：SCC#1 = {4}，SCC#2 = {1, 2, 3}
✨ 解题步骤详解
- 建图：注意是有向图，只加单向边。
- 选择算法：Tarjan 一次 DFS 完成，代码更紧凑；Kosaraju 需要建反图但思路清晰。
- 缩点应用：求出 SCC 后，常见的后续操作是将每个 SCC 缩为一个点，得到一个 DAG（有向无环图），然后在 DAG 上进行拓扑排序、DP 等操作。
- 典型问题：
- 求 DAG 中入度为 0 的 SCC 数量（最少需要多少个起点才能到达所有点）。
- 求 DAG 中出度为 0 的 SCC 数量（有多少个"汇"）。
- 加最少的边使整个图强连通。
✨ 常见错误
- Tarjan 中忽略 in_stack 判断：对于已访问但不在栈中的节点（属于已完成的 SCC），不应用其更新 low 值。
- Kosaraju 忘记建反图：第二次 DFS 必须在反图上进行。
- 混淆有向图和无向图：SCC 是有向图的概念，无向图中应该用连通分量或双连通分量。
- 缩点后建新图时加了重边：缩点后应注意去重边。
- DFS 栈溢出：节点数很大时（>10^5），递归 DFS 可能栈溢出，可考虑手写栈模拟。
✨ 算法评价
| 指标 | Tarjan | Kosaraju |
|---|---|---|
| 时间复杂度 | O(V + E) | O(V + E) |
| 空间复杂度 | O(V + E) | O(V + E)（额外存反图） |
| DFS 次数 | 1 次 | 2 次 |
| 实现难度 | 中等 | 较简单 |
| 竞赛常用度 | 高 | 中 |
SCC 是有向图分析的核心工具。缩点后的 DAG 结构使许多看似困难的有向图问题变得容易处理，是竞赛中的高频考点。