GESP 七级 · GESP 202406 C++ 七级 第 9 题

下面关于图的说法正确的是（ ）。

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

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

【考点】图论基础｜强连通图｜图的度

1. 🎯 考纲定位 本题考查《GESP 大纲》七级图论模块，卡住的是"图定义理解不精确"这个通病——七级学生容易把简单概念复杂化，或者用直觉替代定义。

2. 🧠 解题思维

• A 错在"不同顶点"：无向图中两个顶点间可连两条边形成 2 顶点环，定义里没要求顶点数≥3
• B 错在"至少另一个顶点"：有向图允许自环，单顶点经自环到自身也是环
• C 错在"任意两个顶点存在边"：这描述的是完全图，完全图虽强连通，但强连通不要求完全（只需单向可达），偷换概念
• D 对：每条边贡献 1 入度 1 出度，总度数和 = 2|E|，这是图论铁律

3. 🪤 陷阱拆解 最阴险的是 C 选项——"任意"两个字制造完美假象，学生凭"完全图肯定强连通"的直觉选 C，命题人就是赌你"碰巧没想反例"。A 和 B 的陷阱在于把定义里的"简单环"默认成"简单图"，七级学生容易混淆"简单环"和"无重边"这两个概念。

4. 🔄 反命题思维 如果把 C 改成"如果任意两个顶点之间都存在一条边，且无重边无自环"，答案还是 C。刷到图定义题先问自己：命题人是在考我记住定义，还是在考我理解定义背后的结构？