专题：强连通分量与缩点 —— 把环团压成一个点

本讲定位：图论系列第十三讲，有向图连通性的第一讲。本讲要解决的是一个非常具体的困境：有向图上有环，就没法拓扑排序，也就没法 DP。解决办法只有一句话——把互相可达的点团整个缩成一个点，图立刻变成 DAG，然后就回到你已经会的那一套。 Tarjan 算法本身十五行，真正要理解的是那个 low 数组的语义和”栈里的点意味着什么”，本讲会把这两件事讲透，并用实测反例说明为什么少一个 instk 判断就会错。文中所有代码均经 g++ -O2 -std=c++14 -Wall 编译运行，Tarjan 模板与 Floyd 传递闭包暴力做了 4500 组随机对拍，两道例题各与独立实现的暴力对拍 3000 组。

前置知识：图的存储（邻接表，第 01 讲）；DFS 及递归栈（第 02 讲）；拓扑排序与 DAG 上递推（第 04 讲，本讲第 8 节直接用）。不需要学过割点/桥。

适合对象：CSP-S 复赛。CSP-J 学生可以只读第 1–3 节建立概念（初赛会考定义），模板部分不必强求。标 ⭐ 的小节为选修或后续讲次的引子。

1. 从一道题说起

P2341 受欢迎的牛：$n$ 头奶牛，给出 $m$ 对关系 $(a, b)$，表示”奶牛 $a$ 认为奶牛 $b$ 很受欢迎”。这种关系是可传递的：$a$ 认为 $b$ 受欢迎、$b$ 认为 $c$ 受欢迎，则 $a$ 也认为 $c$ 受欢迎。求有多少头奶牛被所有奶牛认为很受欢迎。数据范围 $n \le 10^4$，$m \le 5 \times 10^4$。

把关系看成有向边 $a \to b$，题目就是问：有多少个点，能被图中所有点到达？

最直接的写法是对每个点 $v$，在反图上从 $v$ 做一次 DFS，看能不能走到全部 $n$ 个点：

for (int v = 1; v <= n; v++) {          // 单次 DFS 是 O(n + m)
    memset(vis, 0, sizeof(vis));
    dfs_on_reverse_graph(v);
    if (count_vis() == n) ans++;
}

复杂度 $O(n(n+m))$，代入数据是 $10^4 \times 6 \times 10^4 = 6 \times 10^8$——稳稳超时。想用 Floyd 求传递闭包更糟，$O(n^3) = 10^{12}$，连边都存不下。

卡住我们的是什么？看这样一组关系：$1 \to 2$、$2 \to 3$、$3 \to 1$。这三头牛互相认为对方受欢迎，它们三个在”谁认为谁受欢迎”这件事上完全等价：任何牛只要能到达其中一个，就一定能到达全部三个；它们能到达的点集也完全相同。我们却把它们当成三个独立的点，各做了一次 DFS。

于是有了本讲的核心思路：

把互相可达的点团缩成一个点。 缩完之后图上不再有任何环（第 3 节会证明），变成一个 DAG；而 DAG 上的可达性、最长路、计数，都是第 04 讲已经解决的问题。

2. 强连通与强连通分量

先把话说准。以下都是有向图上的概念。

• 点 $u$ 与点 $v$ 强连通：既存在 $u \to \cdots \to v$ 的路径，又存在 $v \to \cdots \to u$ 的路径。规定每个点与自身强连通。
• 强连通分量（Strongly Connected Component，SCC）：一个点集，其中任意两点强连通，且再加入任何一个点都不满足这个性质（极大性）。

“强连通”是一个等价关系（自反、对称、传递都成立，传递性用路径拼接即可看出），所以每个点恰好属于一个 SCC，全图的点被唯一地划分成若干个 SCC。这一点很重要：SCC 划分不依赖你从哪里开始搜、用什么算法，它是图本身的性质。

初学最容易混的是它和无向图连通块的区别。看这张图：

① ──→ ②        无向意义下: 一个连通块 {1, 2}
                强连通意义下: 两个 SCC {1} 和 {2}
                           (因为 2 回不到 1)