GESP 七级 · GESP 202503 C++ 七级 第 7 题

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

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

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

【考点】树的结构性质｜强连通图｜最小生成树

1. 🎯 考纲定位 GESP 七年级图论模块，专卡"树的有向化理解"。命题人发现大量考生把"树是有向无环图"与"强连通"混淆，误以为只要连通就是强连通。

2. 🧠 解题思维 逐个验证选项：

• A 正确：树确实是有向无环图，但 DAG 可以是多叉或含多个根
• B 错误：树根→子节点单向，子节点无法反向回父节点，不存在任意两节点互相可达，不满足强连通定义
• C 正确：连通图的最小生成树定义就是包含所有 N 个点且无环的 N-1 条边
• D 正确：N+1 个点 N 条边的有向图必含至少一个叶子节点（入度为 0 或出度为 0），无法形成环，故不可能强连通

3. 🪤 陷阱拆解

• 选项 B 最阴险：偷换"连通"与"强连通"概念。考生只看到树是连通的，就以为有向化后也是强连通的
• 选项 D 看似反直觉：N+1 个点 N 条边，直觉觉得"差一条边就能成环"，但命题人利用"有向图成环至少需要 N+1 条边"这一隐蔽事实
• 选项 A 的"但有向无环图不都是一棵树"是绝对化表述，若考生只背结论不思考 DAG 的多种形态，就会误判

4. 🔄 反命题思维 命题人若想考"树的边数"，会直接问 N 个点树的边数；要考"强连通"，必用有向树来制造概念混淆。刷到类似题先问：有向图连通≠强连通，边数与点数的关系是否符合成环条件，命题人多半在偷换术语。