强连通分量,真是个霸气的名字!我相信,当你学会强连通分量后,光是模板就足够让那些 OI 初学者对你感到无比敬佩了——霸气的函数名,超长的代码,优秀的时间复杂度!那么,一起来看看吧,传说中的强连通分量。
我们要学习强连通分量,首先就得知道强连通分量是什么。强连通是神马?分量是神马?让我们把这些看起来晦涩难懂的概念搞清楚吧。
强连通
连通 连通的概念大家都很清楚吧?在一张无向图中,如果两个点 $a$ 和 $b$ 可以互相到达,我们就可以说 $a$ 和 $b$ 是连通的。 在这里,我们可以发现一个明显的事情:那就是连通这个概念是对于 $2$ 个点的,不能对于 $3$ 个点,也不能对于 $1$ 个点。我们不能说 $a$ 是连通的,也不能说 $a,b,c$ 是连通的,但是我们能说 $a,b,c$ 是两两连通的。
“强”是什么?
要知道,我们在研究强连通分量时所研究的图是有向图,也就是我们现在拿到的图应该是一张有向图,而不是无向图。那么在有向图中,连通是怎样定义的呢?
在有向图中,连通分为两种:
弱连通
对于两个点 $a$ 和 $b$,若 $a$ 能到达 $b$ 但 $b$ 不能到达 $a$,则称 $a$ 与 $b$ 弱连通。
强连通
对于两个点 $a$ 和 $b$,若 $a$ 能到达 $b$ 且 $b$ 也能到达 $a$,则称 $a$ 与 $b$ 强连通。
注意,在这里,连通的定义也是仅仅对于两个点的。
强连通分量