核心概述
强连通分量（Strongly Connected Components, SCC）：将有向图分解为若干子图，使每个子图内任意两点互相可达；将每个分量收缩为点可得到无环的凝聚图（DAG）。典型算法为 Kosaraju（两遍 DFS）或 Tarjan（单遍栈法），复杂度 O(N+M)。
原文引述
Description: Decompose a directed graph into strongly connected components; build the condensation DAG. Implemented via Kosaraju or Tarjan. Time: O(N + M) Status: tested
展开阐述
-
函数/接口（据实现）
- scc(G) → {C, comp}：
- C：分量个数。
- comp[v] ∈ [0, C) 为顶点 v 所在分量编号（常可保证按拓扑序编号，便于后续 DP）。
- 可选：根据 comp 构建凝聚图 DAG（对每条边 u→v，若 comp[u]≠comp[v]，连 comp[u]→comp[v] 并去重）。
- scc(G) → {C, comp}：
-
算法A：Kosaraju（两遍 DFS）
- 在原图上做 DFS，按“退出时间”将顶点压入序列 order。
- 在反图上，按 order 的逆序依次作为起点再做 DFS，访问到的点构成一个强连通分量并赋同一编号。
- 需要构建反图，思路直观，实现简洁。
-
算法B：Tarjan（单遍 + 栈）
- 维护 dfn[u]（时间戳）、low[u]、栈 stk 与 inStack 标记。
- DFS(u) 时：
- dfn[u]=low[u]=timer++，u 入栈。
- 遍历 u→v：
- 若 v 未访问：DFS(v)，low[u]=min(low[u], low[v])。
- 否则若 v 在栈：low[u]=min(low[u], dfn[v])。
- 若 low[u]==dfn[u]：从栈中弹出直到 u，形成一个分量并编号。
- 单遍完成，无需反图，常数因子小。
-
输出语义
- C：强连通分量数。
- comp[v]：顶点 v 的分量编号。
- 凝聚图为 DAG，可在其上进行拓扑排序与 DP。
-
复杂度
- 两种算法均为 O(N+M)；内存开销与图存储一致。
-
使用与注意
- 若需检测是否存在环：判断 C 是否小于 N 或检查 comp[u]==comp[v] 的回边。
- 在 2-SAT 中，若某变量 x 与 ¬x 落在同一分量则无解（见 051-图论-2SAT）。
- 在凝聚图上可配合 078-图论-拓扑排序 做分量级别的 DP。