算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？ 第1页

原图不行，能求出的是一个环但不是回路。求回路有3个经典算法。

1、ISM/AISM

在讲求强连通子集的时候，先了解一个文科生常用的方法，解释结构模型与对抗解释结构模型。

上面一篇是一个艺术设计的，然后发了一篇在计算机刊物中的论文。里面用到了AISM可以去看看。

上面是AISM的一个计算地址，它的第一步就是求强连通分量。

2、求强连通分量的三大算法

kosaraju(克鲁斯克尔)算法是用于求有向图的强连通分量的算法之一

时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。

这个就是题主说的。

Tarjan算法是用于求有向图的强连通分量

Tarjan算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。

时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。

Gabow算法是用于求有向图的强连通分量

Gabow算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。

这个其实就是双指针。

上面三个方法其实是一回事。

上面是三种方法的速度比较。