NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 19 题

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

这题考强连通图的判定，拿到图先别急着删边，而是心里把每条边的‘替代路径’找出来，删掉后还能绕回来才是真强连通。

很多学生会把‘连通’和‘强连通’搞混，以为只要还能走到对方就行，忘了有向图必须双向可达；还有的同学看图不仔细，把边 a 当成关键桥，其实它删了还有另一条路，而 b/c/d 删了就会断掉某个方向的通路，导致误选。

这题考什么

NOIP 普及组这道题核心就是考查强连通图的定义与判定：在一个有向图里，任意两个节点 u、v 都要满足 u 能到 v 且 v 能到 u，这样的图才叫强连通。命题人喜欢拿一张看起来挺‘稠密’的图，然后让你删一条边，判断删完还是不是强连通，其实就是在考你‘这条边是不是冗余的’。

图里到底有哪些边

看原题配图，图里标了四条边：a、b、c、d。我们一条一条来想，删了它之后，剩下的图里还能不能从任意点走到任意点。