CSCI3160 Special 9：强连通分量（历史题面）

来源：教师官网2024 Fall历史题面，p.1，网页检索缓存可读。限制：当前共享sp-ex9.pdf返回零字节；上述历史PDF直接下载返回404，但检索工具返回了完整五题文本。本文对应可读的历史题面，未声称与当前缺失文件逐字相同，也未创建假PDF。结构：每题先题解后解析，均为自行推导。

Problem 1：不同SCC互不相交

若两个强连通分量共享顶点z，则任一分量中的点都能经z到另一个分量的任意点，反向也可。因此两者并集强连通；由极大性它们必须是同一个SCC，故不同SCC不相交。

设u在第一分量，v在第二分量。第一分量内部给u→z、z→u，第二分量给z→v、v→z，拼接得到u→v与v→u。这补上了“并集强连通”的具体路径，而不是仅引用名词。

注意普通强连通子图可以重叠；结论需要它们是不可扩大的分量。例如一个三点有向完全图内，任意两点子集都强连通，但它们都不是SCC。

证明逆否：若原图存在从第一SCC某点到第二SCC某点的路径，把路径顶点替换为所属分量并去掉连续重复项，就得到缩点图中的分量路径。因此缩点图不可达时原图也不可能有这种路径。

原图路径中每次从一个分量进入另一个分量，所用边恰好是定义缩点边的依据。分量内走多少步都可以压成停留在同一个缩点。得到的序列若有重复分量，删去重复段仍保留可达性。

自取路径a→b→c→d，其中a,b同属C₁，c属C₂，d属C₃，压缩后C₁→C₂→C₃。证明不要求原路径所有顶点都位于两个端点分量中，中间可以经过任意其他分量。

G中u可达v，当且仅当反图中v可达u。故“u、v互相可达”在反转全部边后不变，这个等价关系的各个类也不变，所以两图SCC划分相同。

一条路径u=x₀→x₁→…→xₖ=v反转成v=xₖ→…→x₀=u；若原本还有返回路径，反图也有另一方向。因此反图不保持单向可达方向，却保持双向互达。单独有a→b时，反图是b→a，两图都分成两个单点SCC，并不因为边反向就合并。

对不同SCC，若缩点路径为C₀→C₁→…→Cₖ，课堂边性质给出label(Cᵢ)>label(Cᵢ₊₁)。连续使用严格大于的传递性，得到label(C₀)>label(Cₖ)。

这里label(C)是该分量内顶点DFS结束标签的最大值，已与L12（本地课件）p.14–15的定义及单边引理核对一致，不是随意选分量里的某个顶点标签。路径必须至少含一条跨分量边；零长度从自己到自己不能推出label(C)>label(C)。缩点图无环也保证两个不同端点间可取没有重复分量的路径。

例如路径标签12、9、4，直接由12>9>4得到12>4。无需重新分析DFS的每条原边，题目要的是把单边结论推广到可达链。

取边a→b、b→c、c→a、b→d。第一遍从a开始，并在b处先访问c再访问d，结束顺序为c、d、b、a。第二遍按最小结束标签从c在原图DFS，会访问c、a、b、d，把全部四点误当一个分量；真实SCC是{a,b,c}与{d}。

第一遍到c时，c→a指向已在递归栈里的灰点，不再递归，所以c先结束；返回b后才发现d，d随后结束；最后b、a结束。因此最小标签落在非汇分量内，并没有保证它的分量是缩点图汇点。

第二遍c→a→b能继续沿b→d走出去，而d没有回到a,b,c的路径，故“本次DFS访问全部就是一个SCC”的判断失败。这个例子只需四点，且明确指定第一遍邻接顺序，是算法允许的一次合法执行，足以否定无条件正确性。

给 Q5 的反例补全发现与完成时刻。 沿正文顺序，从 a 开始，在 b 处先访问 c，再访问 d，每发生一次发现或完成事件就把时钟加 1：

顶点	发现时刻	完成时刻	实际 SCC
a	1	8	$\{a,b,c\}$
b	2	7	$\{a,b,c\}$
c	3	4	$\{a,b,c\}$
d	5	6	$\{d\}$

c 看到 a 时 a 是灰色，不会再递归；c 先结束，随后才访问 d。最小完成点 c 所属分量仍有 b→d 这条出边，故第二遍在原图从 c 出发会错误合并两个 SCC。真正用于缩点排序的是一个分量内的最大完成时刻，这里分别为 8 和 6；不能用最小完成点替换这个量。

自测：保留完成递减顺序，却忘记反图，是否足够？

仍不够。这里首根 a 在原图可达 d，第二遍同样会合并两分量。顶点顺序与反图方向是相互配合的算法条件，不能只保留其中一个。

五题对应上述官网历史PDF的检索缓存p.1，核验日期2026-09-30。题干仅作短概述，证明与反例独立撰写；未据此认定当前学期的Sp09版本。