GESP 八级 · GESP 202503 C++ 八级 第 4 题

下列关于树和图的说法，错误的是（ ）。

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

注意题目问的是"错误的是"还是"正确的是"，避免看反。选项中若有绝对化表述通常错误。

() 解析：

【考点】树的结构性质｜有向无环图（DAG）｜强连通图

🎯 考纲定位：本题出自 GESP 八级《图论》模块（P5.3 树与图的关系），命题人专门卡住"树≠任意 DAG"的常见误区。绝大多数考生看到"无环"就自动联想到"树"，却忽略树还要求"无向连通且任意两点间仅有一条路径"，这是图论中最容易被偷换概念的地方。

🧠 解题思维：逐项拆解——A 项前半句"树是有向无环图"成立（把根→子节点的有向边视为 DAG），但后半句"所有 DAG 都是树"显然荒谬，因为 DAG 可以有多棵子树、甚至无根；B 项把树看作有向图，每个节点指向子节点，由于树本身无向连通，弱连通性自然成立；C 项 N 个顶点连通的无向图，其生成树必须恰好包含 N-1 条边，这是生成树定义直接推得；D 项 N+1 个顶点、N 条边的有向图，若要强连通则至少需要 N+1 条边（每个点都要有一条出边且构成环），因此不可能。

🪤 陷阱拆解：A 项最阴险，命题人用"有向无环图"这张大网兜住所有树，却故意留了"都是一棵树"这个绝对化表述，考纲里树必须是"无向连通且任意两点间唯一路径"的结构，DAG 可以有多根、有孤立点、甚至根本无根；B 项看似简单，但考生容易忽略"弱连通"的定义，误以为只要原图连通就行，实则弱连通要求忽略方向后仍连通，树恰好满足；C 项的陷阱是忘记"连通"前提，若图不连通则不存在生成树，命题人故意省略了"连通"二字，考验考生对生成树定义的严谨性；D 项考查强连通图的边数下限，很多考生只记住"强连通图至少 N 条边"，却不知在有向图中 N+1 个顶点必须至少 N+1 条边才能形成强连通结构，这是典型的边界条件陷阱。

🔄 反命题思维：若把 D 项改成"N 个顶点、N 条边的有向图一定不是强连通的"，答案会反转，因为 N 个顶点 N 条边可以构成强连通图（如环）；若把 C 项去掉"连通"二字，答案也会变，因为不连通图不存在生成树。刷到类似题时，先问自己"命题人想考我什么"，是概念混淆、边界条件还是计数下限，再决定从哪一步切入。