强连通分量，真是个霸气的名字！我相信，当你学会强连通分量后，光是模板就足够让那些 OI 初学者对你感到无比敬佩了——霸气的函数名，超长的代码，优秀的时间复杂度！那么，一起来看看吧，传说中的强连通分量。

思想引领

我们要学习强连通分量，首先就得知道强连通分量是什么。强连通是神马？分量是神马？让我们把这些看起来晦涩难懂的概念搞清楚吧。

• 强连通

  • 连通 连通的概念大家都很清楚吧？在一张无向图中，如果两个点 $a$ 和 $b$ 可以互相到达，我们就可以说 $a$ 和 $b$ 是连通的。 在这里，我们可以发现一个明显的事情：那就是连通这个概念是对于 $2$ 个点的，不能对于 $3$ 个点，也不能对于 $1$ 个点。我们不能说 $a$ 是连通的，也不能说 $a,b,c$ 是连通的，但是我们能说 $a,b,c$ 是两两连通的。

  • “强”是什么？

    要知道，我们在研究强连通分量时所研究的图是有向图，也就是我们现在拿到的图应该是一张有向图，而不是无向图。那么在有向图中，连通是怎样定义的呢？

    在有向图中，连通分为两种：

    1. 弱连通

       对于两个点 $a$ 和 $b$，若 $a$ 能到达 $b$ 但 $b$ 不能到达 $a$，则称 $a$ 与 $b$ 弱连通。

    2. 强连通

       对于两个点 $a$ 和 $b$，若 $a$ 能到达 $b$ 且 $b$ 也能到达 $a$，则称 $a$ 与 $b$ 强连通。

    注意，在这里，连通的定义也是仅仅对于两个点的。

• 强连通分量