强连通分量 (SCC)

在有向图 $G = (V, E)$ 中，如果对于每一对顶点 $u, v \in V$ ，都存在从 $u$ 到 $v$ 以及从 $v$ 到 $u$ 的路径，则称 $G$ 是强连通的。有向图的强连通分量（Strongly Connected Components, SCC）是其极大的强连通子图。

基础概念

在学习如何求 SCC 之前，我们需要了解 DFS 搜索树中的边分类。在一个有向图的 DFS 过程中，边可以分为以下四类：

树边：DFS 森林中实际经过的边。
后向边：指向祖先节点的边。
前向边：指向子树中非直接后代节点的边。
横叉边：从一个子树指向另一个已访问子树的边。

性质：如果节点 $u$ 是某个 SCC 中第一个被访问到的节点，那么该 SCC 的所有其他节点一定都在以 $u$ 为根的 DFS 子树中。

Tarjan 算法

Tarjan 算法是基于 DFS 的线性时间算法，用于寻找图中的所有 SCC。它为每个节点维护两个关键值：

dfn[u]：节点 $u$ 被搜索到的次序（时间戳）。
low[u]：节点 $u$ 通过搜索树或回溯到栈中节点所能到达的最小 dfn。

算法流程

按照 DFS 顺序访问节点，并将其入栈，同时标记节点在栈中。
初始化 dfn[u] = low[u] = ++timestamp。
遍历 $u$ $u$ 的所有邻接点 $v$ $v$ ：
- 如果 $v$ 未访问过：递归访问 $v$ ，并用 low[v] 更新 low[u]。
- 如果 $v$ 已访问且在栈中：用 dfn[v] 更新 low[u]。
在回溯时，如果发现 dfn[u] == low[u]，说明 $u$ 是当前 SCC 的根。此时将栈中 $u$ 及其上方的节点全部弹出，这些节点构成一个 SCC。

实现 (C++)

cpp

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

struct Tarjan {
    int n;
    int timestamp;
    int scc_cnt;
    vector<vector<int>> adj;
    vector<int> dfn, low, scc;
    vector<bool> in_stack;
    stack<int> st;

    Tarjan(int n) : n(n), timestamp(0), scc_cnt(0), 
                    adj(n + 1), dfn(n + 1, 0), low(n + 1, 0), 
                    scc(n + 1, 0), in_stack(n + 1, false) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
    }

    void run(int u) {
        dfn[u] = low[u] = ++timestamp;
        st.push(u);
        in_stack[u] = true;

        for (int v : adj[u]) {
            if (!dfn[v]) {
                run(v);
                low[u] = min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            scc_cnt++;
            while (true) {
                int v = st.top();
                st.pop();
                in_stack[v] = false;
                scc[v] = scc_cnt;
                if (u == v) break;
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; ++i) {
            if (!dfn[i]) run(i);
        }
    }
};

应用：缩点

强连通分量最常见的应用是将有向图中的每个 SCC 缩成一个点。缩点后的图必然是一个有向无环图（DAG）。

在 DAG 上，我们可以方便地进行拓扑排序、动态规划等操作。例如，求解有向图中权值最大的路径（允许重复经过点，但点权只计一次）时，可以先缩点，然后在生成的 DAG 上求最长路。

缩点实现步骤

使用 Tarjan 算法找出所有 SCC。
遍历原图的所有边 $(u, v)$ $(u, v)$ ：
- 如果 scc[u] != scc[v]，则在缩点后的新图中添加一条边 scc[u] -> scc[v]。
对新图（DAG）进行处理。

总结

Tarjan 算法的时间复杂度为 $O(V + E)$ ，空间复杂度为 $O(V + E)$ 。理解 dfn 和 low 的定义以及栈在算法中的作用是掌握该算法的关键。

强连通分量 (SCC) ​

基础概念 ​

Tarjan 算法 ​

算法流程 ​

实现 (C++) ​

应用：缩点 ​

缩点实现步骤 ​

总结 ​