求强连通分量的方法:
第一种Kosaraju算法:
(1)第一次对图G进行dfs遍历,并在遍历过程中,记录每一个点的退出顺序
如果以1为起点遍历,访问结点的顺序如下:
1 2 3 5 5 3 2 1 4 4 1 结点第二次访问即退出时,那么我们可以得到结点的退出顺序
5 3 2 4 1
(2)倒置这个图,按照退出顺序的逆序对反图进行第二次dfs遍历 1 4 (退出)2 3 5 (退出)
每次遍历得到的那些点属于同一个强连通分量
第二种Tarjan
另一个挺好的讲解