NOIP 普及 2011 第一轮 第 19 题：删除边后仍保持强连通

题目

对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（   ）后，它依然是强连通的。

选项

• A. a
• B. b
• C. c
• D. d

答案

A

题解

考点定位

本题考「强连通性冗余边」,对应大纲 3.3.3 强连通（难度【3】）。

解题过程

依原卷图：删除某条边后仍保证所有点互达。逐边检验「该边是否是某些点对互达的唯一通道」：不在任何「割」位置的边可删。按原图边 a/b/c/d 的角色，可删的是冗余回路上的边。

选 A。

易错提醒

① 强连通图的每条边都在某个环上，但删边后仍强连通需整个图仍强连通——用「删边后逐点对检查可达性」或找图中至少两个独立环覆盖；② 原卷配图题，考试时直接按图判断每个点入度出度 ≥1 且环冗余。