CSCI3160 Regular 8：强连通分量、反图与缩点 DP

原件：题目（本地课件）；官方答案（本地课件） p.1–2。定位：把有环图的互相依赖压成 DAG，再在线性时间内传播可达信息。

SCC 指极大的强连通顶点集合。“极大”是不能再加入顶点而保持强连通，不是全图中顶点最多。以下所有线性复杂度都以邻接表为前提。

Problem 1：缩点图为什么无环（答案 p.1）

每个 SCC 缩成一个节点，只保留不同 SCC 之间的有向边。反设这些分量节点形成有向环 C₁→C₂→…→Cₖ→C₁。沿环可以从任一分量到达任一其他分量；在每个分量内部又可在任意两个顶点之间移动。因此这些分量的并集强连通，原本每个分量都可以扩大，违反极大性。

需要先说明路径能穿过分量：进入某个分量的顶点未必就是下一条跨边的起点，但强连通性保证能在内部走过去。不能只把图形上的环当作原图中恰有相同顶点序列的环。

自取 {a,b} 内有双向边，且 b→c、c→d。缩点链是 {a,b}→{c}→{d}。若再加 d→a，三组其实合并为同一个 SCC，不能仍保留三个节点组成环。

Problem 2：线性构造反图（答案 p.1）

对每个顶点创建一个空列表 rev[u]。遍历原图每条 u→v，把 u 加到 rev[v]。于是 rev[v] 中记录的正是所有原图中指向 v 的顶点，也就是反图中 v 的出邻居。

为所有 u 建立空 rev[u]
对每个 u：
    对 adj[u] 中每个 v：
        将 u 加入 rev[v]

每个点初始化一次、每条边搬一次，时间和输出空间都是 O(n+m)。用链表头插或可摊还常数追加的数组；若每次为找尾部走完整条链表，便失去线性保证。

例：a→b、a→c、c→b，反图为 b→a、c→a、b→c。孤立顶点也要创建空列表，不能在输出中消失。

Problem 3：两遍 DFS 的线性实现（答案 p.1）

第一遍在 G 上做完整 DFS 森林，不只从某一个源点搜一次。每个顶点退出递归、所有出边处理完时，追加到 finish 数组。然后按 Q2 构造反图，并将所有访问标记清空。

第二遍从 finish 的末尾往前扫描；遇到尚未访问的点就在反图启动 DFS，并给此次 DFS 新访问的所有点标同一个分量编号。每棵 DFS 树恰好是一个 SCC。

排序无需比较排序：finish 本来就是按结束顺序产生，倒序读即可。选下一次根的扫描指针只向前走，不要每次从头查找最晚结束白点，否则可能多花 O(n²)。两次 DFS、反图和数组扫描合计 O(n+m)。

为什么要反图：原图某个 SCC 到后继分量的边在反图里朝回，按结束时间从大到小选择可以让本轮只访问当前未标记 SCC 内部，而不会误吞另一个未处理分量。每个 SCC 内反转所有路径仍互达，因此本轮又能访问该分量全部点。

用 a↔b、b→c 作例子：原图从 a 搜起，退出次序可为 c,b,a；反图从 a 开始能访问 b，却不能走向 c，于是先输出 {a,b}，再从 c 输出 {c}。

Problem 4：DAG 每点可达的最小权重（答案 p.1）

定义 W(u) 为 u 能到达的所有顶点（包括自身）中的最小权重。任何可达路径要么长度零停在 u，要么第一步进入某个出邻居 v。因此

W(u)=\min\bigl(\{w_u\}\cup\{W(v):u\to v\}\bigr).

由于依赖的是出邻居，要逆拓扑序计算。初始化 W(u)=w_u，然后遍历每条出边 u→v，做 W(u)=min(W(u),W(v))。当 u 计算时 v 已完成。顶点 O(n)、边 O(m)，总 O(n+m)。孤立点与汇点的答案就是自己的权重，负权也不影响取最小。

自取链 a→b→c，权重 7、−2、5：倒序先得 W(c)=5，再得 W(b)=−2，最后 W(a)=−2。如果遗漏自身候选，b 会错成 5。

Problem 5：一般有向图用 SCC 消除循环依赖（答案 p.2）

若 u、v 属于同一 SCC，则二者互达。u 能到达的任意点 z，v 可先到 u 再到 z；反向同理，故两者可达集合完全相同，也应有相同答案。

步骤如下：先求 SCC；为每个分量 C 计算分量权重 $w_C=\min_{u\in C}w_u$ ；遍历每条原边，把跨分量边加入缩点邻接表；对缩点 DAG 用 Q4 逆拓扑 DP；最后每个原顶点读取自己分量的答案。

缩点过程中可以保留平行跨边：总条数不超过原边数，多次执行同一个 min 不影响答案，所以仍为 O(n+m)，不必为了去重引入 O(m log m) 排序。若使用入度拓扑排序，入度统计与减一也都按保留边逐条处理即可。

自取图 a↔b、b→c、c→d，权重 8、6、9、−1。分量初始权重为 6、9、−1，逆序传播后都是 −1；a、b 的答案相同，原图虽然有环，整个计算仍是线性。

正确性连接。 原图路径可压成分量图的路径；分量图路径也能借助分量内互达性展开为原图路径。因此“可达的分量最小权重”与“可达的原顶点最小权重”完全一致，而不只是一个上界。

补充：缩点后传播的顺序与身份。 用文中 a↔b、b→c、c→d 例子，令分量ID为C1={a,b}、C2={c}、C3={d}。先以原权8、6、9、−1聚合，得(6,9,−1)，再按C3,C2,C1依次计算：C3取−1；C2取min(9,−1)=−1；C1取min(6,−1)=−1。最后按每个点的分量ID回填，而不是把分量数组直接当作四个原点的数组。

自测：两个 SCC 间有多条平行边，拓扑排序统计入度后能只减一次吗？

若入度逐条统计了三条边，就必须逐条减三次；若只减一次，会把本已无未处理前驱的点卡在正入度。可以先去重再统计，也可以始终保留多重边，但计数口径要一致。DP里重复min无害，不意味着拓扑入度可以不配对。

来源与证据

官方题目及答案 p.1–2。例子为本解析自取，时间界按完整邻接表操作计数。本文不据练习推断考试范围。