强连通分量
高级强连通分量缩图后可把任意有向图变成 DAG。
// 算法讲解
强连通分量
输入节点数和有向边，观察 Tarjan 算法找强连通分量。
待机
速度 中
待机 ⌨1void tarjan(int u, vector<vector<int>>& adj,
2 vector<int>& dfn, vector<int>& low,
3 stack<int>& stk, vector<bool>& onStack,
4 int& timer, vector<vector<int>>& sccs) {
5 dfn[u] = low[u] = ++timer;
6 stk.push(u); onStack[u] = true;
7 for (int v : adj[u]) {
8 if (!dfn[v]) {
9 tarjan(v, adj, dfn, low, stk, onStack, timer, sccs);
10 low[u] = min(low[u], low[v]);
11 } else if (onStack[v])
12 low[u] = min(low[u], dfn[v]);
13 }
14 if (low[u] == dfn[u]) {
15 vector<int> comp;
16 while (true) {
17 int v = stk.top(); stk.pop();
18 onStack[v] = false;
19 comp.push_back(v);
20 if (v == u) break;
21 }
22 sccs.push_back(comp);
23 }
24}
复杂度分析
时间 O(V + E)
空间 O(V)
最优 O(V + E)
最坏 O(V + E)
算法讲解
强连通分量（SCC）是有向图中的一个极大子图，子图中任意两个节点都可以互达。
Tarjan 算法用一次 DFS，借助时间戳和 low 数组在 O(V+E) 内找出所有 SCC。
Kosaraju 算法做两次 DFS：第一次在原图上记录后序，第二次在反图上按后序逆序访问。
把每个 SCC 缩成一个点后，原图变成一个 DAG，这是 2-SAT 和有向图分析的基础。