强连通分量与 2-SAT

前言

在无向图中，连通性很简单——两个点之间有路径就算连通。但有向图不同：$A$ 能到 $B$，不代表 $B$ 能到 $A$。想象城市中的单行道——从东区能开车到西区，但回来可能要走完全不同的路。

强连通分量（Strongly Connected Component, SCC）是指有向图中”互相可达”的极大子图。在 SCC 内部，任意两个节点都能互相到达。把每个 SCC 缩成一个”超级节点”后，整张图变成一个 DAG——这意味着 SCC 是有向图中最基本的”循环单元”。

为什么 SCC 这么重要？因为它揭示了有向图的深层结构。很多问题在有环图上无解，但在 DAG 上有解。SCC 缩点后，有向图变成了 DAG，就可以用拓扑排序 + DP 求解了。

SCC 还有一个出人意料的应用：2-SAT 问题（每个变量出现两次的布尔可满足性问题）。把逻辑约束转化为”蕴含图”，然后求 SCC——如果某个变量和它的否定在同一个 SCC 中，就说明矛盾，问题无解。

问题的本质

有向图和无向图的连通性有什么区别？

无向图中，连通性是对称的——$u$ 能到 $v$，$v$ 就能到 $u$。所以无向图的连通分量（Connected Component）只需要 BFS/DFS 就能求。

有向图中，$u$ 能到 $v$ 但 $v$ 不能到 $u$ 是很常见的。强连通分量要求双向可达：$u$ 能到 $v$ 且 $v$ 能到 $u$。这比无向图的连通性强得多。

一个关键性质：把每个 SCC 缩成一个点后，有向图变成 DAG（无环）。为什么？因为如果缩点后的图中还有环，那环上的所有 SCC 应该合并成一个更大的 SCC——与”极大”矛盾。

Kosaraju 算法：为什么要跑两遍 DFS？

求 SCC 有多种算法（Kosaraju、Tarjan、Garbow），其中 Kosaraju 最直观：

1. 在原图上跑 DFS，记录每个节点的完成时间（后序）
2. 把完成时间从大到小排序
3. 在反图（所有边反转）上按这个顺序跑 DFS，每次 DFS 访问到的所有节点构成一个 SCC

为什么需要反图？ 这是一个精妙的观察。原图中，SCC 内部的节点互相可达。但在 SCC 之间，只存在单向的边。反转所有边后，SCC 内部的边依然互通（双向的怎么反转都通），但 SCC 之间的边方向反了——原来能”出去”的变成了”只能进来”。

所以反图上 DFS 会”被困在”当前 SCC 中，无法跳到其他 SCC。这正是我们想要的——每次 DFS 恰好访问一个完整的 SCC。

为什么按完成时间的逆序？ 原图 DFS 的完成顺序和拓扑序有关——“被别人指向的”SCC 完成得更晚。按逆序处理，保证了我们先处理”没有出边”的 SCC，避免在反图上”泄漏”到其他 SCC。

2-SAT：逻辑问题怎么变成图问题？

2-SAT 是这样的问题：有 $N$ 个布尔变量 $x_1, x_2, \ldots, x_N$，每个约束是两个文字（变量或其否定）的或，如 $(x_1 \lor \neg x_2)$。问是否存在一组赋值满足所有约束。

核心转化：每个约束 $(a \lor b)$ 等价于两个蕴含：$\neg a \to b$ 和 $\neg b \to a$。（因为如果 $a$ 为假，$b$ 必须为真，反之亦然。）

把每个变量 $x_i$ 拆成两个节点：$x_i$（真）和 $\neg x_i$（假）。对每个约束建两条有向边。然后在这个”蕴含图”上求 SCC。

关键判定：如果 $x_i$ 和 $\neg x_i$ 在同一个 SCC 中，说明 $x_i \to \neg x_i$ 且 $\neg x_i \to x_i$——$x_i$ 为真则它必须为假，为假则必须为真，矛盾！所以无解。反之，如果不冲突，就可以从 SCC 的拓扑序中反推出一组赋值。

理论 + 代码

Kosaraju 算法

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN], radj[MAXN]; // ① 原图和反图
bool visited[MAXN];
vector<int> order; // DFS 完成顺序
int scc_id[MAXN];  // 每个节点属于哪个 SCC
int scc_cnt = 0;

void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfs1(v);
    order.push_back(u); // ② 后序记录
}

void dfs2(int u) {
    scc_id[u] = scc_cnt;
    for (int v : radj[u])
        if (scc_id[v] == -1) dfs2(v);
}

void kosaraju(int N) {
    // 第 1 遍：原图 DFS，记录完成顺序
    for (int i = 1; i <= N; i++)
        if (!visited[i]) dfs1(i);
    reverse(order.begin(), order.end()); // ③ 逆序 = 拓扑序近似

    // 第 2 遍：反图 DFS，按逆序处理
    fill(scc_id, scc_id + N + 1, -1);
    for (int u : order) {
        if (scc_id[u] == -1) {
            dfs2(u); // ④ 每次DFS访问一个SCC
            scc_cnt++;
        }
    }
}

逐行解析：

• ① 需要同时维护原图和反图。读入时每条边加两次：adj[a].push(b) 和 radj[b].push(a)。
• ② 后序记录：DFS 退出时才加入 order。这意味着”被别人指向的”节点后记录——和拓扑排序的后序翻转是同一个原理。
• ③ 逆序处理。为什么要翻转？因为后序的完成顺序是”叶子先完成”（拓扑逆序），翻转后变成”根先处理”。
• ④ 反图上 DFS 时，不需要 visited——用 scc_id == -1 判断未访问。每次 DFS 访问的所有节点构成一个 SCC。

2-SAT 求解

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 400006; // 2*N 个节点（变量和否定各一个）
vector<int> adj[MAXN], radj[MAXN];
bool visited[MAXN];
vector<int> order;
int scc_id[MAXN], scc_cnt;

// 变量 x 的真节点编号 = 2*x，假节点编号 = 2*x+1
int var_true(int x) { return 2 * x; }
int var_false(int x) { return 2 * x + 1; }

// 添加蕴含 a → b
void add_implies(int a, int b) {
    adj[a].push_back(b);
    radj[b].push_back(a);
}

// 添加约束 (a ∨ b)，等价于 ¬a→b 和 ¬b→a
void add_clause(int a, int b) {
    add_implies(a ^ 1, b); // ① ¬a → b（异或 1 翻转真假）
    add_implies(b ^ 1, a); // ② ¬b → a
}

bool solve_2sat(int N) {
    // Kosaraju
    for (int i = 0; i < 2 * N; i++)
        if (!visited[i]) /* dfs1 同上 */ ;
    // 反图 DFS 同上
    // ...
    // 判定：x 和 ¬x 不能在同一个 SCC
    for (int i = 0; i < N; i++) {
        if (scc_id[var_true(i)] == scc_id[var_false(i)])
            return false; // ③ 矛盾！
    }
    return true;
}

逐行解析：

• ①② 每个约束 $(a \lor b)$ 生成两条蕴含边。编号技巧：x ^ 1 把真变假、假变真（因为 2k ^ 1 = 2k+1，2k+1 ^ 1 = 2k）。
• ③ 如果变量 $x_i$ 的真节点和假节点在同一个 SCC 中，说明存在 $x_i \to \neg x_i$ 和 $\neg x_i \to x_i$ 的路径——$x_i$ 必须同时为真和为假，矛盾。

走一遍 Kosaraju

有向图：1→2, 2→3, 3→1, 3→4, 4→5, 5→4

第一遍 DFS（原图）：

dfs(1) → dfs(2) → dfs(3) → dfs(4) → dfs(5) → 完成5 → 完成4 → 完成3 → 完成2 → 完成1
order = [5, 4, 3, 2, 1]

翻转后处理顺序：[1, 2, 3, 4, 5]

第二遍 DFS（反图）：反图的边：2→1, 3→2, 1→3, 4→3, 5→4, 4→5

dfs(1): 访问 1→3→2 (反图 1→3, 3→2)。但 2→1 的反向呢？1→3→2→? 不，反图中 2→1 不存在...
实际上反图中 1→3, 3→2, 2→1 构成环：1→3→2→1
所以 dfs(1) 访问 {1, 2, 3}，SCC 0
dfs(4): 反图中 4→5, 5→4 构成环，访问 {4, 5}，SCC 1

缩点后：SCC0 → SCC1（原图的 3→4 变成 SCC0 → SCC1），DAG。

例题

例题 1：T90 021 — Come Back in One Piece（★5）

题目：$N$ 个顶点 $M$ 条边的有向图。求满足”顶点 $x$ 能到 $y$，且 $y$ 也能到 $x$“的点对 $(x, y)$ 的数量（$1 \le x < y \le N$）。

数据范围：$2 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$

—— AtCoder Typical 90 021

分析：互相可达 = 在同一个 SCC 中。所以答案 = $\sum \binom{s}{2}$，其中 $s$ 是每个 SCC 的大小。

代码：

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN], radj[MAXN];
bool visited[MAXN];
vector<int> order;
int scc_id[MAXN], scc_cnt;

void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfs1(v);
    order.push_back(u);
}

void dfs2(int u, int id) {
    scc_id[u] = id;
    for (int v : radj[u])
        if (!scc_id[v]) dfs2(v, id);
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);   // ① 原图
        radj[b].push_back(a);  // ② 反图
    }
    // ③ Kosaraju
    for (int i = 1; i <= N; i++)
        if (!visited[i]) dfs1(i);
    for (int i = order.size() - 1; i >= 0; i--) {
        int u = order[i];
        if (!scc_id[u]) {
            scc_cnt++;
            dfs2(u, scc_cnt);
        }
    }
    // ④ 统计每个 SCC 的大小
    vector<int> sz(scc_cnt + 1, 0);
    for (int i = 1; i <= N; i++) sz[scc_id[i]]++;
    // ⑤ 答案 = sum of C(s, 2)
    long long ans = 0;
    for (int k = 1; k <= scc_cnt; k++)
        ans += (long long)sz[k] * (sz[k] - 1) / 2;
    printf("%lld\n", ans);
    return 0;
}

逐行解析：

• ①② 读入时同时建原图和反图，Kosaraju 需要。
• ③ 两遍 DFS：第一遍记录后序，第二遍在反图上按逆后序处理。
• ④⑤ 统计每个 SCC 的大小。同一 SCC 内 $\binom{s}{2}$ 对互相可达的点对。

验证样例 1：$N=4, M=7$。SCC 为 $\{1,2,4\}$ 和 $\{3\}$。$\binom{3}{2} + \binom{1}{2} = 3 + 0 = 3$。✓

---

例题 2：ACL Practice G — SCC

题目：$N$ 个顶点 $M$ 条边的有向图（编号 $0$ 到 $N-1$）。求强连通分量分解，按拓扑序输出。

数据范围：$1 \le N, M \le 5 \times 10^5$

—— AtCoder ACL Practice G

分析：SCC 模板题。题目要求按拓扑序输出——Kosaraju 第二遍 DFS 自然按拓扑序给出（先找到的 SCC 在拓扑序中靠后，需要反转）。

代码（使用 Tarjan，因为只需一次 DFS）：

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 500006;
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], timer_val;
bool onstack[MAXN];
stack<int> stk;
vector<vector<int>> sccs;

void tarjan(int u) {
    disc[u] = low[u] = ++timer_val;
    stk.push(u); onstack[u] = true;
    for (int v : adj[u]) {
        if (!disc[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (onstack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (low[u] == disc[u]) {               // ① SCC 根
        vector<int> comp;
        while (true) {
            int v = stk.top(); stk.pop();
            onstack[v] = false;
            comp.push_back(v);
            if (v == u) break;
        }
        sccs.push_back(comp);              // ② 记录 SCC
    }
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
    }
    for (int i = 0; i < N; i++)
        if (!disc[i]) tarjan(i);
    // ③ Tarjan 天然按拓扑逆序给出 SCC，需要反转
    reverse(sccs.begin(), sccs.end());
    printf("%d\n", (int)sccs.size());
    for (auto& comp : sccs) {
        printf("%d", (int)comp.size());
        for (int v : comp) printf(" %d", v);
        printf("\n");
    }
    return 0;
}

逐行解析：

• ① 当 low[u] == disc[u] 时，$u$ 是 SCC 的根，弹出栈中 $u$ 上方所有节点。
• ② 每个 SCC 存入 sccs 数组。
• ③ Tarjan 天然按拓扑逆序给出（因为先处理完子树再标记 SCC）。反转后即为拓扑序。

---

例题 3：ACL Practice H — Two SAT

题目：$N$ 面旗帜，每面可以放在位置 $X_i$ 或 $Y_i$。任意两面旗帜间距 $\ge D$。判断是否有解，有解则输出方案。

数据范围：$1 \le N \le 1000$

—— AtCoder ACL Practice H

分析：这是经典的 2-SAT 问题。变量 $x_i$ = 旗帜 $i$ 放在 $X_i$（真）还是 $Y_i$（假）。约束：如果旗帜 $i$ 放在 $a_i$，旗帜 $j$ 放在 $b_j$ 时距离 $< D$，则不能同时选——添加子句 $\neg(i \text{ 在 } a_i) \lor \neg(j \text{ 在 } b_j)$。

代码：

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 4006; // 2 * N * 2
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], timer_val;
bool onstack[MAXN];
stack<int> stk;
int scc_id[MAXN], scc_cnt;

void tarjan(int u) {
    disc[u] = low[u] = ++timer_val;
    stk.push(u); onstack[u] = true;
    for (int v : adj[u]) {
        if (!disc[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (onstack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (low[u] == disc[u]) {
        scc_cnt++;
        while (true) {
            int v = stk.top(); stk.pop();
            onstack[v] = false;
            scc_id[v] = scc_cnt;
            if (v == u) break;
        }
    }
}

int main() {
    int N, D;
    scanf("%d%d", &N, &D);
    int X[1006], Y[1006];
    for (int i = 0; i < N; i++)
        scanf("%d%d", &X[i], &Y[i]);
    // ① 建图：2-SAT
    // 节点 2i = x_i 选 X_i, 2i+1 = x_i 选 Y_i
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            // 检查所有 4 种组合
            auto add = [&](int a, int b) {
                adj[a ^ 1].push_back(b); // ¬a → b
                adj[b ^ 1].push_back(a); // ¬b → a
            };
            // ② 如果 i 选 X_i 且 j 选 X_j 时距离 < D
            if (abs(X[i] - X[j]) < D) add(2*i, 2*j);
            if (abs(X[i] - Y[j]) < D) add(2*i, 2*j+1);
            if (abs(Y[i] - X[j]) < D) add(2*i+1, 2*j);
            if (abs(Y[i] - Y[j]) < D) add(2*i+1, 2*j+1);
        }
    }
    // ③ Tarjan 求 SCC
    for (int i = 0; i < 2 * N; i++)
        if (!disc[i]) tarjan(i);
    // ④ 检查矛盾
    for (int i = 0; i < N; i++) {
        if (scc_id[2*i] == scc_id[2*i+1]) {
            printf("No\n");
            return 0;
        }
    }
    // ⑤ 构造解：scc_id 小的赋 false
    printf("Yes\n");
    for (int i = 0; i < N; i++) {
        // scc_id[2i] < scc_id[2i+1] 意味着 2i 在 DAG 中更靠后 → 赋 true
        if (scc_id[2*i] > scc_id[2*i+1]) printf("%d\n", X[i]); // 2i 的 SCC 编号大 → 选 X
        else printf("%d\n", Y[i]); // 2i+1 的 SCC 编号大 → 选 Y
    }
    return 0;
}

逐行解析：

• ① 每面旗帜两个选择：节点 $2i$ 代表放 $X_i$，节点 $2i+1$ 代表放 $Y_i$。
• ② 对每对旗帜 $(i, j)$，检查 4 种放置组合。如果某种组合的间距 $< D$，则添加子句”不能同时这样放”，即 $\neg a \lor \neg b$ → 两条边 $\neg(\neg a) \to \neg b = a \to \neg b$ 和 $b \to \neg a$。
• ③④ 标准 2-SAT 判定：如果 $x_i$ 和 $\neg x_i$ 在同一 SCC，无解。
• ⑤ Tarjan 编号大的 SCC 在 DAG 中更靠前（拓扑序更早）。选 SCC 编号大的那个——这保证了不会出现矛盾。

---

例题 4：T90 059 — Many Graph Queries（★7）

题目：$N$ 个顶点 $M$ 条边的有向图（$X_i < Y_i$）。$Q$ 个查询：顶点 $A_j$ 到 $B_j$ 是否可达？

—— AtCoder Typical 90 059

分析：$N, Q \le 10^5$。先用 SCC 缩点，得到 DAG。在 DAG 上，对每个 SCC 预处理可达性（由于 $X_i < Y_i$，DAG 中边都是从小编号指向大编号，具有特殊结构）。查询时只需检查 $A_j$ 所在 SCC 是否能到达 $B_j$ 所在 SCC。

（★7 练习题，核心思路：SCC 缩点后利用边的特殊性质（$X_i < Y_i$）做可达性查询。）

参考文献

理论讲义 — AtCoder Algorithm Lectures

• グラフ理論用語集（强连通、SCC 定义）

模板练习 — ACL Practice Contest

• G SCC（SCC 模板题，Tarjan/Kosaraju）【例题】
• H Two SAT（2-SAT 建图+求解）【例题】

实战练习 — 競プロ典型 90 問

• 021 Come Back in One Piece（★5，SCC 对计数）【例题】
• 059 Many Graph Queries（★7，子图 SCC）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化