GESP 七级 · GESP 202512 C++ 七级 第 15 题

下面这个有向图的强连通分量的个数是（ ）。


强连通分量（SCC）：有向图中任意两点互相可达的最大子图。Tarjan算法基于DFS和low数组，时间复杂度O(n+m)。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】图论基础｜强连通分量｜Tarjan算法

【考纲定位】图论基础｜强连通分量｜Tarjan/Kosaraju算法。命题人卡住的是考生对"传递闭包"本质的模糊——只背算法流程，却不会手动拆解图结构，导致在复杂图中遗漏独立分量。GESP七级明确要求掌握强连通分量概念，这是图论模块的第三级进阶点。

【解题思维】看到图先扫孤点：节点1、2无入出边，各成1个SCC（共2个）。再看环：3→4→3构成自环分量（1个）。5→6→7→5构成大环分量（1个）。剩余节点8、9分别连向7和4，无法反向形成环，故各为独立SCC（2个）。合计5个。

【陷阱拆解】选项A(3)是漏算孤点的典型错误——把1、2归入某个环；选项B(4)是混淆了"连通分量"与"强连通分量"，把5→6→7→5误判为两个环；选项D(6)则把8、9分别误算为环内节点。最阴险的是"单点成环"陷阱：节点2虽无入出边，但它在强连通意义下自成1个分量，若只盯着边看就会漏掉。

【反命题思维】若把节点8改为指向5，则8并入5→6→7→5环，答案变4；若把节点2改为指向1，则2并入1的孤立分量，答案仍为5。刷到此类题先问："如果删掉某条边，SCC数会减几？"——这才是命题人想考察的图结构敏感度。