强连通分量 (Kosaraju 算法)¶

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

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

算法原理与核心两步¶

第一轮 DFS（在原图 \(G\) 上）：
遍历所有未访问节点，在 DFS 递归回溯（后序）时将节点压入栈中。
此时，栈顶节点的拓扑序最靠前（属于 DAG 中出度相对靠后的源分量）。
第二轮 DFS（在反图 \(G^T\) 上）：
将原图的所有边反向，得到转置图 \(G^T\)。
依次从栈顶弹出节点。若该节点在反图中未被访问，则从该节点出发在 \(G^T\) 上执行 DFS。
本次 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;
    }
};

LeetCode 经典真题精选与题解提示¶

LeetCode 2360 - 图中的最长环 (Longest Cycle in a Graph) 困难
提示

内向基环树 / 强连通分量找最大简单环。
- 每个节点至多只有一条出边（基环内向树森林）；
- 利用 Kosaraju 或 Tarjan 算法求出所有强连通分量，其中点数 \(> 1\) 的 SCC 即为一个环，取其点数最大值；
- 也可通过时间戳标记直接在单次 DFS 遍历中提取环长。
LeetCode 2127 - 参加会议的最多员工数 (Maximum Employees to Be Invited to a Meeting) 困难
提示

内向基环树环长分类讨论。
- 每个员工喜欢一个人，构成了出度为 1 的内向基环树网络；
- 情况 1（环长 \(\ge 3\)）：整个大环必须自成一桌，无法外挂链，只能单选最大的环；
- 情况 2（环长 \(= 2\)）：互为喜欢的两人可以坐在相邻位置，且两端各自可以挂上一条最长的树枝链。所有 2 元环及其外挂链的长度可以全部相加！
- 利用反向图拓扑排序剥除树枝，求出所有环的大小并按两类分别统计最大值。
LeetCode 802 - 找到最终的安全状态 (Find Eventual Safe States) 中等
提示

反向建图拓扑排序 / 缩点判无环。
- 若从某节点出发的所有可能路径最终都能在没有出边的终端节点结束，则该节点为安全节点（即不在任何环中，也无法走到任何环中）；
- 将所有边反向后，终端节点变为入度为 0 的节点，跑一遍 Kahn 拓扑排序算法，所有能入队的节点即为安全节点。