第 19 章
强连通分量与网络流
第十九章：强连通分量与网络流
上一章我们解决了带权图上的两个经典优化问题——最短路径和最小生成树。这一章我们将进入图论的"高级领地"：强连通分量（Strongly Connected Components, SCC） 和网络流（Network Flow）。
强连通分量揭示了有向图的"宏观结构"——哪些节点之间可以互相到达？如果我们把每个强连通分量"缩"成一个超节点，整个图就变成一个 DAG（有向无环图），问题的复杂度大幅降低。这是图论中"化繁为简"的核心技术。
网络流则是一类看似理论化、实则应用极广的模型。从"管道中最多能流过多少水"到"如何将工人最优地分配给任务"，网络流将大量组合优化问题统一到一个优雅的框架中。最大流最小割定理将"如何最大化流量"和"如何最小化破坏代价"这两个看似无关的问题完美联系在一起。
这一章的核心目标：(1) 掌握 Tarjan 算法求 SCC、割点和桥；(2) 理解 Kosaraju 算法的两次 DFS 设计；(3) 理解最大流问题和 Ford-Fulkerson 方法；(4) 了解二分图匹配与匈牙利算法；(5) 评估这些算法在面试中的考查频率和学习优先级。
Level 1 · 你需要知道的
19.1 强连通分量的概念
强连通：在有向图中，如果节点 u 可以到达 v，且 v 也可以到达 u，则称 u 和 v 是强连通的。
强连通分量（SCC）：一个极大的强连通子图——其中任意两个节点都是强连通的，且不能再加入任何外部节点仍保持强连通。
有向图示例：
0 → 1 → 2
↑ ↓
3 ← 4 ← 2
↓
5 → 6
↑ ↓
8 ← 7
强连通分量：
SCC1: {0, 1, 2, 3, 4} (这5个节点之间任意两个可互达)
SCC2: {5} (只有自己)
SCC3: {6, 7, 8} (6→7→8→6 形成环)
缩点后的 DAG:
SCC1 → SCC2 → SCC3
为什么 SCC 重要？
- 简化问题：将 SCC 缩成单个节点后，原图变为 DAG。DAG 上的许多问题（拓扑排序、最长路径等）比一般有向图简单得多。
- 2-SAT 问题：判定布尔表达式可满足性（2-SAT）可以直接归约为 SCC 问题。
- 可达性分析：SCC 内部的节点互相可达，只需分析 SCC 之间的可达性。
19.2 Tarjan 算法
Tarjan 算法是求 SCC 最经典、最高效的方法。它只需要一次 DFS，时间复杂度 O(V + E)。
核心概念：
- DFS 序（dfn）：节点被首次访问的时间戳。
- low 值：从当前节点出发，通过树边或回边，能到达的 DFS 序最小的祖先节点的 dfn 值。
- 栈：维护当前 DFS 路径上所有"还没确定归属 SCC"的节点。
关键判断：如果 dfn[u] == low[u]，说明 u 是某个 SCC 的"根"——从 u 出发无法回到更早的祖先。此时从栈顶弹出直到 u（包括 u），这些节点组成一个 SCC。
from typing import List, Dict, Set
def tarjan_scc(graph: Dict[int, List[int]], n: int) -> List[List[int]]:
"""
Tarjan 算法求强连通分量
参数:
graph: 有向图邻接表
n: 节点数量 (0 到 n-1)
返回:
所有 SCC 的列表（每个 SCC 是一个节点列表）
"""
dfn = [0] * n # DFS 序
low = [0] * n # low 值
on_stack = [False] * n
stack = []
timer = [0] # 用列表模拟可变变量
sccs = []
def dfs(u: int):
timer[0] += 1
dfn[u] = low[u] = timer[0]
stack.append(u)
on_stack[u] = True
for v in graph.get(u, []):
if dfn[v] == 0: # 未访问
dfs(v)
low[u] = min(low[u], low[v])
elif on_stack[v]: # 在栈中 = 在当前 SCC 候选中
low[u] = min(low[u], dfn[v])
# u 是 SCC 的根
if dfn[u] == low[u]:
scc = []
while True:
v = stack.pop()
on_stack[v] = False
scc.append(v)
if v == u:
break
sccs.append(scc)
# 处理所有未访问的节点（图可能不连通）
for i in range(n):
if dfn[i] == 0:
dfs(i)
return sccs
# 使用示例
graph = {
0: [1],
1: [2],
2: [3],
3: [0, 4],
4: [5],
5: [6],
6: [4, 7],
7: []
}
sccs = tarjan_scc(graph, 8)
print("强连通分量:", sccs)
# 可能输出: [[7], [4, 6, 5], [0, 3, 2, 1]]
# 注意: SCC 的输出顺序是逆拓扑序
迭代版本（避免递归深度限制）：
import sys
def tarjan_scc_iterative(graph: Dict[int, List[int]], n: int) -> List[List[int]]:
"""Tarjan 算法的迭代实现 - 避免递归栈溢出"""
dfn = [0] * n
low = [0] * n
on_stack = [False] * n
stack = []
timer = [0]
sccs = []
for start in range(n):
if dfn[start] != 0:
continue
# 手动模拟递归栈: (节点, 邻居迭代器位置)
call_stack = [(start, 0)]
timer[0] += 1
dfn[start] = low[start] = timer[0]
stack.append(start)
on_stack[start] = True
while call_stack:
u, idx = call_stack[-1]
neighbors = graph.get(u, [])
if idx < len(neighbors):
call_stack[-1] = (u, idx + 1)
v = neighbors[idx]
if dfn[v] == 0:
timer[0] += 1
dfn[v] = low[v] = timer[0]
stack.append(v)
on_stack[v] = True
call_stack.append((v, 0))
elif on_stack[v]:
low[u] = min(low[u], dfn[v])
else:
# u 的所有邻居处理完毕
if dfn[u] == low[u]:
scc = []
while True:
v = stack.pop()
on_stack[v] = False
scc.append(v)
if v == u:
break
sccs.append(scc)
call_stack.pop()
if call_stack:
parent = call_stack[-1][0]
low[parent] = min(low[parent], low[u])
return sccs
19.3 割点与桥
割点（Articulation Point / Cut Vertex）：如果删除某个节点（及其关联边）后，图的连通分量数增加，则该节点是割点。
桥（Bridge / Cut Edge）：如果删除某条边后，图的连通分量数增加，则该边是桥。
割点和桥揭示了图的"脆弱点"——网络中的关键节点/链路。
def find_bridges_and_articulation_points(graph: Dict[int, List[int]], n: int):
"""
使用 Tarjan 算法思路求无向图的割点和桥
注意：这是在无向图上运行的！
"""
dfn = [0] * n
low = [0] * n
timer = [0]
bridges = []
articulation_points = set()
def dfs(u: int, parent: int):
timer[0] += 1
dfn[u] = low[u] = timer[0]
children = 0 # u 在 DFS 树中的子节点数
for v in graph.get(u, []):
if v == parent:
continue # 忽略来时的边（无向图）
if dfn[v] == 0: # 树边
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
# 桥判定：v 无法不经过 (u,v) 到达 u 或 u 的祖先
if low[v] > dfn[u]:
bridges.append((u, v))
# 割点判定（非根情况）
if parent != -1 and low[v] >= dfn[u]:
articulation_points.add(u)
else:
# 回边
low[u] = min(low[u], dfn[v])
# 根节点的割点判定：DFS 树中有 ≥2 个子节点
if parent == -1 and children >= 2:
articulation_points.add(u)
for i in range(n):
if dfn[i] == 0:
dfs(i, -1)
return bridges, articulation_points
# 示例
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2, 4],
4: [3, 5, 6],
5: [4, 6],
6: [4, 5]
}
bridges, aps = find_bridges_and_articulation_points(graph, 7)
print("桥:", bridges) # [(2, 3), (3, 4)] 或类似
print("割点:", aps) # {2, 3, 4} 或类似
判定逻辑解释：
- 桥：对于树边 (u, v)，如果
low[v] > dfn[u]，说明从 v 的子树中无法通过回边到达 u 或 u 的祖先——删除 (u, v) 后 v 的子树将断开。 - 割点（非根）：对于树边 (u, v)，如果
low[v] >= dfn[u]，说明 v 的子树无法不经过 u 到达 u 的祖先——删除 u 后 v 的子树将断开。 - 割点（根）：根节点是割点当且仅当它在 DFS 树中有 ≥2 个子节点（删除根后这些子树互不连通）。
19.4 最大流问题概述
问题定义：给定一个有向图（流网络），有一个源点 s 和一个汇点 t，每条边有一个容量上限。求从 s 到 t 的最大流量。
约束条件：
- 容量限制：每条边的流量 ≤ 容量。
- 流守恒：除 s 和 t 外，每个节点的流入量 = 流出量。
流网络示例：
s ---10--→ A ---8--→ t
| ↑ ↘ ↑
5 2 4 6
| | ↘ |
↓ | ↘ |
B ---3--→ C ---6--→ t（B→C 容量3）
最大流 = 能从 s 推到 t 的最大总流量
19.5 Ford-Fulkerson 方法
Ford-Fulkerson 不是一个具体算法，而是一个方法框架：反复找从 s 到 t 的增广路径（augmenting path），沿路径增加流量，直到找不到增广路径为止。
残余图（Residual Graph）：对于每条边 (u, v) 容量 c，流量 f：
- 正向残余容量 = c - f（还能再推多少）
- 反向残余容量 = f（可以"退回"多少流量）
增广路径：残余图中从 s 到 t 的路径。
from collections import deque
def bfs_find_path(residual: List[List[int]], source: int, sink: int, parent: List[int]) -> bool:
"""BFS 在残余图中找增广路径 (Edmonds-Karp)"""
n = len(residual)
visited = [False] * n
visited[source] = True
queue = deque([source])
while queue:
u = queue.popleft()
for v in range(n):
if not visited[v] and residual[u][v] > 0:
visited[v] = True
parent[v] = u
if v == sink:
return True
queue.append(v)
return False
def edmonds_karp(capacity: List[List[int]], source: int, sink: int) -> int:
"""
Edmonds-Karp 算法（Ford-Fulkerson + BFS）
参数:
capacity: capacity[u][v] = 边 (u,v) 的容量
source: 源点
sink: 汇点
返回:
最大流值
"""
n = len(capacity)
# 残余图初始等于容量图
residual = [row[:] for row in capacity]
max_flow = 0
parent = [-1] * n
while bfs_find_path(residual, source, sink, parent):
# 找增广路径的瓶颈容量
path_flow = float('inf')
v = sink
while v != source:
u = parent[v]
path_flow = min(path_flow, residual[u][v])
v = u
# 更新残余图
v = sink
while v != source:
u = parent[v]
residual[u][v] -= path_flow # 正向减少
residual[v][u] += path_flow # 反向增加（允许退流）
v = u
max_flow += path_flow
parent = [-1] * n
return max_flow
# 示例
# 4 个节点: 0=源, 3=汇
capacity = [
[0, 10, 10, 0], # 0→1: 10, 0→2: 10
[0, 0, 2, 8], # 1→2: 2, 1→3: 8
[0, 0, 0, 10], # 2→3: 10
[0, 0, 0, 0]
]
print(edmonds_karp(capacity, 0, 3)) # 18
# 路径1: 0→1→3, 流量 8
# 路径2: 0→2→3, 流量 10
# 总计 18（正好等于 s 的出边容量和 = min(10+10, 8+10) = 18）
Edmonds-Karp 复杂度：O(VE²)。每次 BFS 找最短增广路径保证了最多 O(VE) 次增广。
19.6 二分图最大匹配（匈牙利算法）
二分图（Bipartite Graph）：节点可以分成两组 L 和 R，所有边都连接 L 中的节点和 R 中的节点。
最大匹配：找到最多的边，使得每个节点最多被一条边覆盖。
经典应用：工人分配任务、学生选课匹配、相亲配对等。
def hungarian(graph: Dict[int, List[int]], n_left: int, n_right: int) -> int:
"""
匈牙利算法求二分图最大匹配
参数:
graph: 左侧节点的邻接表，graph[u] = [可匹配的右侧节点列表]
n_left: 左侧节点数 (编号 0 到 n_left-1)
n_right: 右侧节点数 (编号 0 到 n_right-1)
返回:
最大匹配数
"""
# match_right[v] = 与右侧节点 v 匹配的左侧节点（-1 表示未匹配）
match_right = [-1] * n_right
def dfs(u: int, visited: List[bool]) -> bool:
"""尝试为左侧节点 u 找一个匹配"""
for v in graph.get(u, []):
if visited[v]:
continue
visited[v] = True
# 如果 v 未匹配，或者 v 当前匹配的对象能找到其他匹配
if match_right[v] == -1 or dfs(match_right[v], visited):
match_right[v] = u
return True
return False
result = 0
for u in range(n_left):
visited = [False] * n_right
if dfs(u, visited):
result += 1
return result
# 示例：3个工人，4个任务
# 工人0: 可做任务 0, 1
# 工人1: 可做任务 1, 2
# 工人2: 可做任务 2, 3
graph = {
0: [0, 1],
1: [1, 2],
2: [2, 3]
}
print(hungarian(graph, 3, 4)) # 3 (最大匹配: 工人0→任务0, 工人1→任务1, 工人2→任务2)
匈牙利算法的核心思想——增广路径：
当为某个左节点 u 找匹配时，如果直接可选的右节点 v 已被占用，就尝试让 v 当前的匹配对象"让位"（去找其他匹配）。这个"让位"过程递归进行，本质上是在找一条从未匹配节点出发、交替经过非匹配边和匹配边、最终到达未匹配节点的"增广路径"。
时间复杂度：O(V × E)。对每个左节点做一次 DFS，每次 DFS 最多访问所有边。
19.7 完整应用示例
"""
综合示例：社交网络分析
"""
def social_network_analysis():
"""
分析社交网络中的社群结构（SCC = 互相关注的群组）
"""
# 关注关系（有向图）
# 0关注1, 1关注2, 2关注0（互相关注环）
# 3关注4, 4关注3（互相关注对）
# 2关注3（单向）
follow_graph = {
0: [1],
1: [2],
2: [0, 3],
3: [4],
4: [3],
5: [4] # 5只关注4，没人关注5
}
sccs = tarjan_scc(follow_graph, 6)
print("互相关注群组:", sccs)
# [[3, 4], [0, 2, 1], [5]]
# 群组1: {3,4} 互相关注
# 群组2: {0,1,2} 互相关注
# 群组3: {5} 孤立用户
# 缩点后的 DAG 可用于分析信息传播路径
print("群组间的传播方向: 群组{0,1,2} → 群组{3,4}")
print("群组{5} → 群组{3,4}")
def task_assignment():
"""
任务分配问题：最大化完成的任务数
"""
# 5个开发者，6个任务
# 每个开发者能做的任务
developer_skills = {
0: [0, 1, 2], # 开发者0: 前端任务
1: [1, 3], # 开发者1: 部分前端+后端
2: [2, 4], # 开发者2: 前端+数据库
3: [3, 4, 5], # 开发者3: 后端+数据库+运维
4: [5] # 开发者4: 仅运维
}
max_tasks = hungarian(developer_skills, 5, 6)
print(f"最多能同时完成 {max_tasks} 个任务")
# 输出: 最多能同时完成 5 个任务
social_network_analysis()
task_assignment()
Level 2 · 它是怎么运行的
19.8 Kosaraju 算法（两次 DFS）
Kosaraju 算法是另一种求 SCC 的经典方法，概念上比 Tarjan 更直观，但需要两次 DFS。
核心思想：
- 第一次 DFS：在原图上，按 DFS 完成顺序记录节点（后序遍历）。
- 反转图：将所有边方向反转。
- 第二次 DFS：按第一次 DFS 的逆后序（即拓扑排序序），在反转图上做 DFS。每次 DFS 能访问到的节点组成一个 SCC。
为什么正确？ 直觉：
- SCC 内的节点在原图和反转图中都互相可达。
- 按逆后序处理保证了：如果 SCC_A 有边指向 SCC_B（在原图中），那么 SCC_A 会先被处理。在反转图中，这条边变为 SCC_B → SCC_A，所以处理 SCC_A 时不会"跑到" SCC_B 中去。
def kosaraju_scc(graph: Dict[int, List[int]], n: int) -> List[List[int]]:
"""
Kosaraju 算法求强连通分量
参数:
graph: 有向图邻接表
n: 节点数量
返回:
所有 SCC 的列表
"""
# 步骤1：原图 DFS，记录后序遍历顺序
visited = [False] * n
finish_order = [] # 后序遍历顺序
def dfs1(u: int):
visited[u] = True
for v in graph.get(u, []):
if not visited[v]:
dfs1(v)
finish_order.append(u)
for i in range(n):
if not visited[i]:
dfs1(i)
# 步骤2：构建反转图
reverse_graph: Dict[int, List[int]] = {i: [] for i in range(n)}
for u in range(n):
for v in graph.get(u, []):
reverse_graph[v].append(u)
# 步骤3：按逆后序在反转图上 DFS
visited = [False] * n
sccs = []
def dfs2(u: int, scc: List[int]):
visited[u] = True
scc.append(u)
for v in reverse_graph[u]:
if not visited[v]:
dfs2(v, scc)
for u in reversed(finish_order):
if not visited[u]:
scc = []
dfs2(u, scc)
sccs.append(scc)
return sccs
# 测试
graph = {0: [1], 1: [2], 2: [0, 3], 3: [4], 4: [3]}
print(kosaraju_scc(graph, 5))
# [[0, 1, 2], [3, 4]] — 两个 SCC
Tarjan vs Kosaraju 对比：
| 特性 | Tarjan | Kosaraju |
|---|---|---|
| DFS 次数 | 1 | 2 |
| 需要反转图？ | 否 | 是 |
| 额外空间 | 栈 + dfn/low 数组 | 反转图 + finish_order |
| 实现难度 | 较高（low 值理解） | 较低（两次简单 DFS） |
| 面试推荐 | ✓（更高效） | ✓（更好解释） |
| 输出顺序 | 逆拓扑序 | 拓扑序 |
19.9 Tarjan 算法的 low 值详解
low[u] 的准确定义是："从 u 的子树出发，通过恰好一条回边（back edge）或横叉边（cross edge to stack node），能到达的最小 dfn 值。"
容易混淆的点：
# 对于树边 (u → v)：
low[u] = min(low[u], low[v]) # 通过子树 v 能到达的最早祖先
# 对于回边 (u → v)，v 在栈中：
low[u] = min(low[u], dfn[v]) # 注意是 dfn[v]，不是 low[v]！
# 为什么用 dfn[v] 而不是 low[v]？
# 因为回边直接指向 v，能到达的是 v 本身（dfn[v]）
# 如果用 low[v]，会传递性地"穿过"多条回边，可能导致不同 SCC 的节点被错误合并
不过在实际实现中，使用 low[u] = min(low[u], low[v]) 对于回边也是正确的（在大多数情况下）——因为如果 v 在栈中且能通过 v 到达更早的节点，那 v 和 u 一定在同一个 SCC 中。很多实现（包括本章前面的代码）使用 dfn[v] 是因为这是 Tarjan 原论文的定义，理论上更精确。
执行过程追踪：
图: 0→1→2→0, 2→3
DFS 开始于节点 0:
访问 0: dfn[0]=1, low[0]=1, 栈=[0]
访问 1: dfn[1]=2, low[1]=2, 栈=[0,1]
访问 2: dfn[2]=3, low[2]=3, 栈=[0,1,2]
邻居 0: 在栈中，low[2] = min(3, dfn[0]) = min(3,1) = 1
邻居 3: 未访问
访问 3: dfn[3]=4, low[3]=4, 栈=[0,1,2,3]
无邻居
dfn[3]==low[3] → SCC={3}，从栈弹出3，栈=[0,1,2]
low[2] = min(low[2], low[3]) = min(1, 4) = 1
返回到1: low[1] = min(low[1], low[2]) = min(2, 1) = 1
返回到0: low[0] = min(low[0], low[1]) = min(1, 1) = 1
dfn[0]==low[0] → SCC={2,1,0}，从栈弹出直到0
结果: SCC1={3}, SCC2={0,1,2}
19.10 最大流最小割定理
定理（Ford & Fulkerson, 1956）：在任何流网络中，最大流的值等于最小割的容量。
割（Cut）：将节点分为两组 S（包含 s）和 T（包含 t），割的容量 = 所有从 S 到 T 的边的容量之和。
直觉解释：
- 最大流 ≤ 任意割的容量（流量不能超过瓶颈）。
- 当 Ford-Fulkerson 终止时，残余图中 s 无法到达 t。此时，s 在残余图中能到达的节点集合为 S，其余为 T。所有从 S 到 T 的原始边都已满载（否则残余容量 > 0，s 能到达 T 中的节点）。这个割的容量正好等于最大流。
应用：最小割的实际含义
- 网络安全：最少需要切断多少条通信链路才能使 s 和 t 断开连接？
- 图像分割：像素分前景/背景，最小化分割代价。
- 项目选择：选择一组项目使净收益最大（等价于最小割的对偶）。
def find_min_cut(capacity: List[List[int]], source: int, sink: int) -> Tuple[Set[int], Set[int]]:
"""
找最小割：先求最大流，然后在残余图中从 source BFS 找可达节点
"""
n = len(capacity)
residual = [row[:] for row in capacity]
parent = [-1] * n
# 先运行 Edmonds-Karp 得到最终残余图
while bfs_find_path(residual, source, sink, parent):
path_flow = float('inf')
v = sink
while v != source:
u = parent[v]
path_flow = min(path_flow, residual[u][v])
v = u
v = sink
while v != source:
u = parent[v]
residual[u][v] -= path_flow
residual[v][u] += path_flow
v = u
parent = [-1] * n
# 在残余图中从 source BFS 找所有可达节点 = S 集合
visited = [False] * n
queue = deque([source])
visited[source] = True
while queue:
u = queue.popleft()
for v in range(n):
if not visited[v] and residual[u][v] > 0:
visited[v] = True
queue.append(v)
S = {i for i in range(n) if visited[i]}
T = {i for i in range(n) if not visited[i]}
# 最小割的边 = 从 S 到 T 且原始容量 > 0 的边
cut_edges = []
for u in S:
for v in T:
if capacity[u][v] > 0:
cut_edges.append((u, v, capacity[u][v]))
return S, T, cut_edges
19.11 Dinic 算法
Dinic 算法是比 Edmonds-Karp 更高效的最大流算法。核心改进：不是每次只找一条增广路径，而是先 BFS 构建分层图（level graph），然后在分层图上用 DFS 一次找多条增广路径。
def dinic(capacity: List[List[int]], source: int, sink: int) -> int:
"""
Dinic 算法求最大流
时间复杂度: O(V²E)，对单位容量图为 O(E√V)
"""
n = len(capacity)
residual = [row[:] for row in capacity]
def bfs_level() -> bool:
"""BFS 构建分层图（level 数组）"""
nonlocal level
level = [-1] * n
level[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v in range(n):
if level[v] == -1 and residual[u][v] > 0:
level[v] = level[u] + 1
queue.append(v)
return level[sink] != -1
def dfs_blocking(u: int, pushed: int) -> int:
"""在分层图上 DFS 找阻塞流"""
if u == sink:
return pushed
while iter_ptr[u] < n:
v = iter_ptr[u]
if level[v] == level[u] + 1 and residual[u][v] > 0:
flow = dfs_blocking(v, min(pushed, residual[u][v]))
if flow > 0:
residual[u][v] -= flow
residual[v][u] += flow
return flow
iter_ptr[u] += 1
return 0
max_flow = 0
level = [-1] * n
while bfs_level():
iter_ptr = [0] * n
while True:
flow = dfs_blocking(source, float('inf'))
if flow == 0:
break
max_flow += flow
return max_flow
Dinic vs Edmonds-Karp 复杂度对比：
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| Edmonds-Karp | O(VE²) | 通用 |
| Dinic | O(V²E) | 通用（更快） |
| Dinic (单位容量) | O(E√V) | 二分图匹配等 |
为什么 Dinic 更快？ 每次 BFS 后，从 source 到 sink 的最短路径长度至少增加 1（因为阻塞流封锁了当前最短路层级）。最短路径最多为 V-1，所以最多做 V-1 次 BFS。每次 BFS + 阻塞流的时间为 O(VE)，总计 O(V²E)。
19.12 二分图匹配的网络流视角
匈牙利算法本质上是在二分图上找增广路径——这和网络流的增广路径方法完全一致！实际上，二分图最大匹配可以直接归约为最大流问题：
构造流网络：
1. 添加超级源 s，连接到所有左侧节点（容量 1）
2. 添加超级汇 t，所有右侧节点连接到 t（容量 1）
3. 原图中 L→R 的边，容量设为 1
最大流 = 最大匹配
s → L1 → R1 → t
s → L2 → R2 → t
s → L3 → R3 → t
(交叉连接省略)
König 定理：在二分图中，最大匹配数 = 最小顶点覆盖数。这是最大流最小割定理在二分图上的特例。
证明思路：最大匹配 = 网络中最大流 = 网络中最小割。而在这个特殊网络中，最小割对应一组容量为 1 的边被切断，每条边对应一个节点被"覆盖"。
19.13 缩点后的 DAG 应用
SCC 缩点后得到 DAG，可以进一步解决：
- 可达性查询：DAG 上用拓扑排序 + DP 判断哪些 SCC 之间可达。
- 最长路径：DAG 上的最长路径（关键路径法）。
- 2-SAT：如果变量 x 和 ¬x 在同一个 SCC 中，则无解。
def scc_dag(graph: Dict[int, List[int]], n: int):
"""
缩点：将原图转化为 SCC 的 DAG
"""
sccs = tarjan_scc(graph, n)
# 每个节点属于哪个 SCC
scc_id = [0] * n
for i, scc in enumerate(sccs):
for node in scc:
scc_id[node] = i
# 构建 DAG（SCC 之间的边）
num_sccs = len(sccs)
dag = {i: set() for i in range(num_sccs)}
for u in range(n):
for v in graph.get(u, []):
if scc_id[u] != scc_id[v]:
dag[scc_id[u]].add(scc_id[v])
# 转为列表
dag = {k: list(v) for k, v in dag.items()}
return sccs, scc_id, dag
# 2-SAT 应用示例
def solve_2sat(n: int, clauses: List[Tuple[int, int]]) -> List[bool]:
"""
2-SAT 求解
变量编号 0 到 n-1
正文字 x 编号为 x，负文字 ¬x 编号为 x+n
clauses: [(a, b), ...] 表示 (a ∨ b)
其中 a, b 是文字编号
"""
# 构建蕴含图
# (a ∨ b) 等价于 (¬a → b) ∧ (¬b → a)
total = 2 * n # 正文字 + 负文字
graph = {i: [] for i in range(total)}
def neg(x):
return x + n if x < n else x - n
for a, b in clauses:
graph[neg(a)].append(b) # ¬a → b
graph[neg(b)].append(a) # ¬b → a
sccs = tarjan_scc(graph, total)
scc_id = [0] * total
for i, scc in enumerate(sccs):
for node in scc:
scc_id[node] = i
# 如果 x 和 ¬x 在同一个 SCC 中，无解
for x in range(n):
if scc_id[x] == scc_id[x + n]:
return None # 无解
# 赋值：如果 scc_id[x] > scc_id[¬x]，则 x = True
# （Tarjan 输出逆拓扑序，编号小的在后面）
assignment = [False] * n
for x in range(n):
assignment[x] = scc_id[x] > scc_id[x + n]
return assignment
Level 3 · 规范怎么定义的
19.14 Tarjan 1972 年论文
论文：Robert E. Tarjan, "Depth-First Search and Linear Graph Algorithms", SIAM Journal on Computing, 1972.
这篇论文是图算法领域的里程碑，它系统性地展示了 DFS 的力量。Tarjan 在文中提出了：
- 强连通分量算法（本章的核心）
- 双连通分量算法（割点和桥的识别）
- DFS 的系统性分类：树边、回边、前向边、横叉边
Tarjan 的关键洞察：DFS 产生的搜索树具有非常好的结构性质。在有向图的 DFS 树中，所有非树边要么是回边（指向祖先），要么是前向边（指向后代），要么是横叉边（指向已完全处理的子树）。利用这些性质，可以在 O(V+E) 时间内解决大量图论问题。
low 值的数学定义（Tarjan 原文）：
low(v) = min(
dfn(v),
min{dfn(w) | (u, w) 是一条回边，u 是 v 的后代（含 v 自身）}
)
也就是说，low(v) 是从 v 的子树出发，通过最多一条回边能到达的最早祖先的 DFS 序号。
Tarjan 的学术贡献：Robert Tarjan（1948-）是理论计算机科学的巨匠之一。他的贡献包括：
- 并查集的 O(α(n)) 分析（1975）
- Fibonacci 堆（与 Fredman 合作，1984）
- Splay 树（与 Sleator 合作，1985）
- 强连通分量算法（1972）
- LCA 的离线算法（1979）
他在 1986 年获得图灵奖（与 John Hopcroft 共同获得），表彰他们在算法和数据结构方面的基础性贡献。
19.15 最大流最小割定理（Ford & Fulkerson 1956）
论文：L.R. Ford Jr. & D.R. Fulkerson, "Maximal Flow through a Network", Canadian Journal of Mathematics, 1956.
背景：这个定理的提出有冷战背景。Ford 和 Fulkerson 在 RAND Corporation 工作，该定理最初用于分析苏联铁路网络的瓶颈容量——即需要切断多少条铁路线才能瘫痪苏联的运输系统。
定理的形式化陈述：
设 f* 是网络中的最大流，C* 是最小割的容量。则 f* = C*。
证明框架：
-
弱对偶性（f ≤ C 对任意流 f 和割 C）：
- 任何从 s 到 t 的流 f 必须完全"通过"任何 s-t 割。
- 流通过割的量 ≤ 割的容量（因为每条割边的流量 ≤ 容量）。
- 因此 |f| ≤ cap(S, T) 对任何割 (S, T)。
-
强对偶性（存在 f, C 使得 f = C）：
- 当 Ford-Fulkerson 终止时，残余图中 s 无法到达 t。
- 定义 S = {在残余图中 s 可达的节点}，T = V \ S。
- 从 S 到 T 的所有原始边都满载（残余容量 = 0）。
- 从 T 到 S 的所有原始边流量为 0（否则有反向残余容量让 s 到达 T 中节点）。
- 所以 |f| = cap(S, T)。加上弱对偶性，f 是最大流，(S,T) 是最小割。
Ford-Fulkerson 方法的终止性问题：
如果容量都是整数，每次增广至少增加 1 单位流量，所以最多 |f*| 次增广，算法终止。但如果容量是无理数，Ford-Fulkerson（使用 DFS 找增广路径）可能不终止！Zwick (1995) 构造了这样的反例。
Edmonds-Karp（使用 BFS）保证终止且复杂度为 O(VE²)，与容量大小无关。
19.16 网络流在实际中的应用
应用 1：二分图匹配（前面已讨论）
应用 2：项目选择问题
有 n 个项目，每个项目有收益 p_i（可正可负）。项目之间有依赖关系：如果选择项目 i，则必须选择项目 j。求最大净收益。
转化为最小割：
- 源 s 连接正收益项目（容量 = 收益）
- 负收益项目连接汇 t（容量 = |收益|）
- 依赖关系 i→j 添加容量 ∞ 的边
- 最大净收益 = 所有正收益之和 - 最小割
应用 3：图像分割
像素分前景/背景。每个像素有属于前景的"偏好值"和属于背景的"偏好值"，相邻像素属于不同类的"惩罚值"。
转化为最小割：
- s → 像素：容量 = 属于前景的偏好值
- 像素 → t：容量 = 属于背景的偏好值
- 相邻像素之间：容量 = 不同类的惩罚值
应用 4：棒球淘汰问题
判断某支球队是否已经被数学淘汰（即使赢下所有剩余比赛也不可能获得冠军）。这可以用最大流来判断！
19.17 匈牙利算法的历史
匈牙利算法（Hungarian Algorithm）最早由 Harold Kuhn 在 1955 年提出，但他的算法基于匈牙利数学家 Dénes König（1931）和 Jenő Egerváry（1931）的工作。Kuhn 以此命名致敬这些匈牙利数学家。
Kuhn 的原始算法解决的是带权二分图最优匹配（Assignment Problem），时间复杂度 O(n³)。我们在 Level 1 中展示的简化版（无权最大匹配）是基于增广路径的 O(VE) 算法。
Hopcroft-Karp 算法（1973）改进了无权二分图最大匹配的复杂度到 O(E√V)——它的核心思想和 Dinic 算法几乎完全相同（分层图 + 多条增广路径）。
König 定理（1931）：在二分图中，
- 最大匹配 = 最小顶点覆盖
- 最大独立集 = n - 最大匹配
这是 LP 对偶性在组合优化中的经典体现。
19.18 SCC 算法的理论比较
| 算法 | 时间 | 空间 | 遍历次数 | 发表年份 |
|---|---|---|---|---|
| Tarjan | O(V+E) | O(V) | 1 次 DFS | 1972 |
| Kosaraju-Sharir | O(V+E) | O(V+E) | 2 次 DFS + 反转图 | 1981 (Sharir) |
| Path-based (Gabow) | O(V+E) | O(V) | 1 次 DFS | 2000 |
| Dijkstra (partition) | O(V+E) | O(V) | 1 次 DFS | 1976 |
Kosaraju 的算法虽然发表于 Sharir 1981 年的技术报告中，但 Kosaraju 据说在 1978 年的一次讲座中就描述了它（未发表）。
Path-based 算法（Gabow 2000）用两个栈代替 Tarjan 的 low 值数组，概念上更清晰，但实际性能差异微小。
Level 4 · 边界与陷阱
19.19 这些算法在面试中的考查频率
让我们用数据说话。以下是基于 LeetCode 题目标签统计和主流面试经验分享的频率分析：
高频（必须掌握）：
- Dijkstra：LeetCode 标签约 50+ 题，面试常考。变体（minimax、多源）更是隐藏考点。
- 拓扑排序：约 30+ 题，频率极高。
- 并查集（与 MST 相关）：约 70+ 题，高频。
- BFS/DFS：无处不在。
中频（建议掌握）：
- Bellman-Ford/SPFA：约 15 题。当题目提到"负权"必须会。
- Kruskal/Prim (MST)：约 10 题。通常直接套模板。
- 二分图判定：约 10 题。
低频（了解即可，面试中极少直接考）：
- 强连通分量 (Tarjan/Kosaraju)：LeetCode 约 5 题。面试中几乎不考，但竞赛和系统设计面试中可能用到概念。
- 最大流/网络流：LeetCode 约 5 题。面试中极罕见，但是建模能力的终极考验。
- 匈牙利算法：面试中几乎不考。但"能否转化为匹配问题"的思维方式有价值。
- 割点/桥：约 5 题（如 LeetCode 1192）。偶尔在系统设计中用于分析网络脆弱性。
结论：
- Dijkstra + MST (Kruskal) 是面试必备，必须能 20 分钟内默写。
- SCC 和网络流属于"知识储备"，面试中直接考的概率 < 5%。
- 最大流最小割定理的思想在系统设计面试中偶尔有用（瓶颈分析）。
- 如果你准备的是 Google/Meta 等大厂的 hard 面试或竞赛，SCC 和网络流值得深入学习。
19.20 什么时候需要学这些
学习优先级推荐：
优先级 1（面试必备）：
- Dijkstra（及变体）
- BFS/DFS
- 拓扑排序
- 并查集 + Kruskal
优先级 2（进阶加分）：
- Bellman-Ford（负权场景）
- Floyd-Warshall（全源）
- 二分图判定
- Tarjan 求割点/桥
优先级 3（高级/竞赛）：
- SCC (Tarjan/Kosaraju)
- 2-SAT
- 最大流 (Dinic)
- 二分图最大匹配
优先级 4（理论深入/博士级）：
- 最小费用最大流
- 一般图匹配 (Blossom 算法)
- Gomory-Hu 树
- 最大权闭合子图
信号：什么时候你需要用这些算法？
| 问题特征 | 可能的算法 |
|---|---|
| "互相可达的分组" | SCC |
| "删除后图不连通" | 割点/桥 |
| "最多能传输/分配多少" | 最大流 |
| "一一对应的最优匹配" | 二分图匹配 |
| "选/不选的相互依赖" | 2-SAT 或网络流 |
19.21 LeetCode 1192：查找集群内的关键连接
题目：给定 n 个服务器和连接（无向图），找出所有"关键连接"——如果删除后有服务器断开。即求所有桥。
def criticalConnections(n: int, connections: List[List[int]]) -> List[List[int]]:
"""
LeetCode 1192: Critical Connections in a Network
直接用 Tarjan 求桥
"""
graph = {i: [] for i in range(n)}
for u, v in connections:
graph[u].append(v)
graph[v].append(u)
dfn = [0] * n
low = [0] * n
timer = [0]
bridges = []
def dfs(u: int, parent: int):
timer[0] += 1
dfn[u] = low[u] = timer[0]
for v in graph[u]:
if v == parent:
continue
if dfn[v] == 0:
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > dfn[u]:
bridges.append([u, v])
else:
low[u] = min(low[u], dfn[v])
dfs(0, -1)
return bridges
# 测试
n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]
print(criticalConnections(n, connections)) # [[1, 3]]
# 解释: 0-1-2 形成环，删除任一条都不影响连通性
# 但 1-3 是桥，删除后节点3孤立
面试注意：这道题可能遇到递归深度限制（n 可达 10⁵）。生产环境中应使用迭代版本或增大递归限制（sys.setrecursionlimit）。
19.22 实际工程中的应用场景
场景 1：微服务依赖分析（SCC）
def analyze_microservice_dependencies(services: List[str], calls: List[Tuple[str, str]]):
"""
分析微服务之间的循环依赖
如果一组服务形成 SCC（互相调用），它们应该被合并或解耦
"""
# 建立编号映射
name_to_id = {name: i for i, name in enumerate(services)}
n = len(services)
graph = {i: [] for i in range(n)}
for caller, callee in calls:
graph[name_to_id[caller]].append(name_to_id[callee])
sccs = tarjan_scc(graph, n)
# 找出有循环依赖的组（SCC 大小 > 1）
circular_groups = []
for scc in sccs:
if len(scc) > 1:
group_names = [services[i] for i in scc]
circular_groups.append(group_names)
return circular_groups
# 示例
services = ["auth", "user", "order", "payment", "notification"]
calls = [
("auth", "user"), # auth 调用 user
("user", "auth"), # user 调用 auth（循环！）
("order", "payment"), # order 调用 payment
("payment", "notification"),
("notification", "order"), # 循环: order→payment→notification→order
]
groups = analyze_microservice_dependencies(services, calls)
print("循环依赖组:", groups)
# [["order", "notification", "payment"], ["auth", "user"]]
场景 2：CDN 流量分配（网络流）
def cdn_bandwidth_allocation():
"""
简化的 CDN 流量分配问题
多个源服务器 → 多个 CDN 节点 → 用户群
目标：最大化总带宽
"""
# 节点: 0=超级源, 1-3=源服务器, 4-6=CDN节点, 7-9=用户群, 10=超级汇
n = 11
capacity = [[0] * n for _ in range(n)]
# 源服务器容量
capacity[0][1] = 100 # 服务器1 带宽 100Mbps
capacity[0][2] = 80 # 服务器2 带宽 80Mbps
capacity[0][3] = 60 # 服务器3 带宽 60Mbps
# 服务器→CDN 链路容量
capacity[1][4] = 50; capacity[1][5] = 70
capacity[2][4] = 40; capacity[2][6] = 60
capacity[3][5] = 30; capacity[3][6] = 50
# CDN→用户群 链路容量
capacity[4][7] = 60; capacity[4][8] = 30
capacity[5][7] = 40; capacity[5][9] = 50
capacity[6][8] = 45; capacity[6][9] = 35
# 用户群需求
capacity[7][10] = 80
capacity[8][10] = 70
capacity[9][10] = 60
max_bw = edmonds_karp(capacity, 0, 10)
print(f"最大可分配带宽: {max_bw} Mbps")
cdn_bandwidth_allocation()
19.23 常见陷阱与总结
陷阱 1：Tarjan 中的重边处理
# 无向图中，如果存在重边 (u,v) 出现两次
# 不能简单用 "if v == parent: continue" 跳过
# 因为只应跳过一次（来时的那条边），第二条平行边应该被考虑
# 正确做法：用边的编号来避免重复
def dfs_with_edge_id(u, parent_edge_id):
for v, edge_id in graph[u]:
if edge_id == parent_edge_id:
continue # 只跳过来时的那条边
# ...
陷阱 2：递归深度限制
import sys
sys.setrecursionlimit(200000) # 对于 n ≤ 10^5 的图
# 或者使用迭代实现（推荐用于生产环境）
陷阱 3：Edmonds-Karp 的邻接矩阵限制
# 邻接矩阵实现的 Edmonds-Karp 空间为 O(V²)
# 如果 V = 10^5，需要 10^10 字节内存 —— 不可行！
# 大规模网络流必须用邻接表实现
# 面试中如果节点数 ≤ 几百，邻接矩阵实现是最清晰的
# 如果节点数 ≤ 10^4-10^5，必须用邻接表 + 链式前向星
陷阱 4：混淆 SCC 与连通分量
# 无向图的连通分量：简单 BFS/DFS
# 有向图的强连通分量：需要 Tarjan/Kosaraju
# 有向图的弱连通分量：忽略边的方向后的连通分量
# 面试中要确认是有向图还是无向图！
算法速查表：
| 算法 | 问题 | 时间 | 面试频率 |
|---|---|---|---|
| Tarjan (SCC) | 有向图强连通分量 | O(V+E) | 低 |
| Tarjan (桥/割点) | 无向图关键边/点 | O(V+E) | 中低 |
| Kosaraju | 有向图强连通分量 | O(V+E) | 低 |
| Edmonds-Karp | 最大流 | O(VE²) | 极低 |
| Dinic | 最大流 | O(V²E) | 极低 |
| Hungarian | 二分图最大匹配 | O(VE) | 低 |
| Hopcroft-Karp | 二分图最大匹配 | O(E√V) | 极低 |
核心要点：
- SCC 是理解有向图结构的钥匙——缩点后变 DAG，问题简化。
- 网络流是组合优化的瑞士军刀——很多"看起来不像流"的问题可以归约为网络流。
- 最大流 = 最小割——这个对偶性是理解网络流应用的核心。
- 面试中这些算法考得少，但知道它们存在很重要——有些 hard 题只有建模为网络流才能高效解决。
- 实际工程中 SCC 最有用——循环依赖检测、死锁分析、编译器优化都用得到。