强连通分量 (Kosaraju 算法)

在有向图 \(G\) 中，若两个顶点 \(u\) 和 \(v\) 互相可达，则称它们是强连通的。强连通分量 (Strongly Connected Component, SCC) 是有向图中的极大强连通子图。

Kosaraju 算法是求解 SCC 的经典线性时间算法，基于对原图和反向图的两次深度优先搜索（Two-pass DFS），思想直观且实现极为优雅。

---

算法原理与核心两步

1. 第一轮 DFS（在原图 \(G\) 上）：
2. 遍历所有未访问节点，在 DFS 递归回溯（后序）时将节点压入栈中。
3. 此时，栈顶节点的拓扑序最靠前（属于 DAG 中出度相对靠后的源分量）。
4. 第二轮 DFS（在反图 \(G^T\) 上）：
5. 将原图的所有边反向，得到转置图 \(G^T\)。
6. 依次从栈顶弹出节点。若该节点在反图中未被访问，则从该节点出发在 \(G^T\) 上执行 DFS。
7. 本次 DFS 所遍历到的所有未访问节点，恰好构成一个完整的强连通分量 (SCC)！

为什么必须反向？ 在原图中，分量 \(A\) 可能单向到达分量 \(B\)。但将所有边反向后，变为 \(B \to A\)。按照栈中倒序访问时，我们先从源分量出发，在反图中它无法流向其他分量，从而将搜索严格局限在自身分量内部。

---

完整模版实现

时间复杂度：严格 \(\mathcal{O}(V + E)\)，空间复杂度：\(\mathcal{O}(V + E)\)。

#include <vector>
#include <algorithm>

struct Kosaraju {
    int n;
    std::vector<std::vector<int>> adj;    // 原图
    std::vector<std::vector<int>> rev_adj;// 反向图
    std::vector<bool> visited;
    std::vector<int> order;               // 后序遍历栈
    std::vector<int> scc_id;              // 节点所属的 SCC 编号 (0-indexed)
    std::vector<std::vector<int>> sccs;   // 每个 SCC 内包含的节点列表
    int scc_cnt = 0;

    Kosaraju(int n) : n(n), adj(n), rev_adj(n), visited(n, false), scc_id(n, -1) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        rev_adj[v].push_back(u); // 构造反向边
    }

    // 第一遍 DFS: 记录完成时间后序
    void dfs1(int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs1(v);
            }
        }
        order.push_back(u);
    }

    // 第二遍 DFS: 在反图上收集 SCC
    void dfs2(int u, int id) {
        scc_id[u] = id;
        sccs[id].push_back(u);
        for (int v : rev_adj[u]) {
            if (scc_id[v] == -1) {
                dfs2(v, id);
            }
        }
    }

    void solve() {
        // 1. 原图 DFS
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs1(i);
            }
        }

        // 2. 反图遍历，栈顶先出
        std::reverse(order.begin(), order.end());
        for (int u : order) {
            if (scc_id[u] == -1) {
                sccs.push_back({});
                dfs2(u, scc_cnt++);
            }
        }
    }

    // 缩点建新 DAG 图 (去除自环与重复边)
    std::vector<std::vector<int>> build_dag() {
        std::vector<std::vector<int>> dag(scc_cnt);
        for (int u = 0; u < n; ++u) {
            for (int v : adj[u]) {
                if (scc_id[u] != scc_id[v]) {
                    dag[scc_id[u]].push_back(scc_id[v]);
                }
            }
        }
        for (int i = 0; i < scc_cnt; ++i) {
            std::sort(dag[i].begin(), dag[i].end());
            dag[i].erase(std::unique(dag[i].begin(), dag[i].end()), dag[i].end());
        }
        return dag;
    }
};