知识点-Tarjan
强连通分量:在一个图的子图中,任意两个点相互可达,也就是存在互通的路径,那么这个子图就是强连通分量(或者称为强连通分支)。如果一个有向图的任意两个点相互可达,那么这个图就称为强连通图。
当我们实现基于dfs的Tarjan算法时,我们用D[i]记录节点i被访问的时间(别的博客用dfn[i]),用F[i]记录节点i或i的子树最小可以返回到的节点j的D[j](别的博客用low[i])。
让我们模拟一下dfs的过程,每个节点上左边的是D的值,右边的是F的值。

首先从节点1开始往下深搜,每次搜索都更新D值和F值,此时F值是节点本身。

当搜索到节点4时,已经无法继续搜索。而此时D值=F值,所以我们可以判定一个强连通分量(在代码中,需要借助“栈”来寻找强连通分量中所有节点),这个强连通量就是节点4。
从图我们也可以看出,节点4无法到达其它任意节点。

