强连通分量

一句话算法

Tarjan SCC 用栈维护当前 DFS 路径上的候选点，当 low[u] == dfn[u] 时，u 到栈顶就是一个强连通分量。

问题模型

在有向图中，如果两个点 $u,v$ 满足：

• $u$ 能到达 $v$；
• $v$ 也能到达 $u$；

则它们强连通。极大的强连通点集叫强连通分量，简称 SCC。

求 SCC 后，常见下一步是缩点：把每个 SCC 看成一个点，原图会变成一张 DAG。

核心直觉

DFS 时，栈里保存的是“已经访问，但还没有确定所属 SCC”的点。

low[u] 表示从 u 出发，沿 DFS 树边和返祖/横叉边，能回到的最早栈内点。

如果：

说明 u 的子树没有办法回到 u 之前的栈内点。于是从 u 到栈顶这一段点互相可达，形成一个完整 SCC。

算法步骤

1. 初始化 dfn[u] = 0，栈为空。
2. DFS 到点 u：
   • 令 dfn[u] = low[u] = ++timer；
   • 把 u 入栈，并标记 in_stack[u] = true。
3. 枚举有向边 u -> v：
   • 若 v 未访问，递归 DFS，并用 low[v] 更新 low[u]；
   • 若 v 在栈中，用 dfn[v] 更新 low[u]。
4. 如果 low[u] == dfn[u]，不断弹栈直到弹出 u，这些点属于同一个 SCC。
5. 对所有未访问点重复 DFS，处理不连通图。

算法证明

核心不变量：栈中的点是已经访问但尚未确定 SCC 的点。

1. 如果边 u -> v 指向未访问点，v 子树能回到的最早栈内点也能被 u 通过 v 到达，所以用 low[v] 更新 low[u]。
2. 如果 v 已访问且仍在栈中，说明 u 能到达一个未归属的祖先或同层候选点，所以用 dfn[v] 更新 low[u]。
3. 当 low[u] == dfn[u]，u 的 DFS 子树无法回到 u 之前的栈内点。此时栈顶到 u 的所有点都能通过 DFS 树边被 u 所在结构连接，又能通过 low 所代表的返祖关系回到同一段中。
4. 这段点对外不能再和更早的栈内点合并，所以它是一个极大的强连通分量。

因此出栈时得到的每一组点都是 SCC，且每个点只会出栈一次。

复杂度分析

设点数为 $n$，边数为 $m$。

• 时间复杂度：$O(n+m)$。
• 空间复杂度：$O(n+m)$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

        struct TarjanScc {
    int n, timer;
    std::stack<int> st;
    bool in_stack[maxn];
    int dfn[maxn], low[maxn], scc_id[maxn];
    int scc_cnt; // SCC 的总数

    void set(int _n) {
        n = _n;
        timer = scc_cnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(in_stack, 0, sizeof(in_stack));
    }

    // 有向图,不要加father参数
    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

        for (int i = e.h[u]; ~i ; i = e[i].next) {
            int v = e[i].v;
            if (!dfn[v]) { // 如果 v 没被访问过
                dfs(v);
                
                // 根据子节点的 low 值更新当前节点的 low 值
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) { //返祖边, 如果 v 在栈中，说明构成了环
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        // 如果 dfn == low，说明找到了一个 SCC 的起始点
        if (low[u] == dfn[u]) {
            scc_cnt++;
            while (1) {
                int v = st.top(); st.pop();
                in_stack[v] = 0;
                scc_id[v] = scc_cnt; // 标记所属 SCC 编号
                if (v == u) break; // 直到找到起始点
            }
        }
    }

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

测试用例

输入图：

5 6
1 2
2 3
3 1
3 4
4 5
5 4

强连通分量为：

{1,2,3}
{4,5}

1,2,3 互相可达，4,5 互相可达；两个 SCC 之间只有从前者到后者的方向。

应用分类详解

SCC 的本质是把有向图中的环状互达结构压成一个点。

一、有向图缩点

典型模式： 有向图里存在环，需要把互相可达的点合并。

识别信号： 出现“强连通”“缩点”“有向图变 DAG”。

核心建模： 每个 SCC 缩成一个点，跨 SCC 的边形成 DAG。

二、判断两个点是否在同一个有向环结构中

典型模式： 判断两个点是否互相可达。

识别信号： 题面要求“能互相到达”“是否处在同一个循环依赖中”。

核心建模： 如果 scc_id[u] == scc_id[v]，则两点互相可达。

三、2-SAT 的基础组件

典型模式： 布尔变量约束，判断是否存在合法取值。

识别信号： 出现“每个变量二选一”“若 A 则 B”。

核心建模： 建蕴含图后，如果变量和它的反变量在同一 SCC，则无解。

经典例题

1. luogu-P3387

缩点模板题。SCC 缩点后在 DAG 上做最长路/DP。

2. poj-2186

受欢迎的牛。缩点后若只有一个出度为 0 的 SCC，则答案是它的大小。

3. luogu-P4782

2-SAT 模板题。SCC 用来判断变量与反变量是否冲突。