题13
题目
在如下图所示的有向图中, 共有 ( ) 个强连通分量.
A. 1
B. 2
C. 3
D. 4
分析
强连通分量和连通分量的区别是，前者是对有向图描述的，后者是对无向图描述的
他们的共同点就是，两者都是某种“子图”，也就是虽然叫做分量，但是本质上是一个图
解
B
强连通分量是极大强连通子图, 任意两个顶点之间有方向相反的两条路径。
由定义不难得出, 若一个顶点只有出边或入边, 则该顶点必定单独构成一个连通分量。
图中, 顶点 B 只有出边, 其他所有顶点都不可能有到顶点 B 的路径, 所以顶点 B 单独构成一个强连通分量。
在顶点 A、C、D、E 中, 任意两个顶点之间都有方向相反的两条路径, 所以可构成一个强连通分量。