求多少个强连通分量之Kosaraju算法

摘自

概要

被指向的强连通分量的至少一个顶点排在指向这个连通分量的所有顶点前面。所以，我们求解强连通分量的步骤可以分为两步：

（1）对原图取反，从任意一个顶点开始对反向图进行逆后续DFS遍历

（2）按照逆后序遍历顺序，对原图进行DFS遍历，一次DFS遍历中访问的所有顶点都属于同一强连通分量。

DFS的逆后序遍历是指：如果当前顶点未访问，先遍历完与当前顶点相连的且未被访问的所有其它顶点，然后将当前顶点加入栈中，最后栈中从栈顶到栈底的顺序就是我们需要的顶点顺序，也就是拓扑排序。

也就是对取反的图进行拓扑序列的依次dfs并累计count就是有向图的强连通分量