前面我们讲过问题，主要是针对无向图的，而对于有向图我们一般求的是强连通分量，常见的三种解决方式分别是Kosaraju算法，Tarjan算法，和Gabow算法。这里我们先介绍使用Kosaraju算法求有向图的强连通分量问题。

先说一下什么叫强连通分量，在有向图 G 中，如果两个顶点 u，v ，有一条从 u 到 v 的有向路径，同时还有一条从 v 到 u 的有向路径，则称这两个顶点强连通(strongly connected)。

如果有向图 G 的任意两个顶点都强连通，称 G 是一个强连通图。有向图的极大强连通子图，称为强连通分量（strongly connected component，SCC）。

如下图所示，相同颜色的属于同一个强连通分量，因为在相同颜色中任意一个顶点都有到其他顶点（相同颜色）的路径。可以看到顶点 7 和顶点 6 不在同一个强连通分量，虽然顶点 7 有到顶点 6 的路径，但顶点 6 没有到顶点 7 的路径。

打开网易新闻 查看精彩图片

如果我们把图中所有的强连通分量缩成一个点，就可以得到一张有向无环图（Directed acyclic graph，DAG），如下所示：

打开网易新闻 查看精彩图片

这个图一定是无环的，如果是有环的，假如蓝色和红色可以构成环，那么蓝色和红色是相互可达的，而同一颜色中的任意两点也都是两两可达的，所以蓝色和红色应该属于同一个强连通分量，这与事实不符。

所以我们可以得出当有向图的所有强连通分量都缩成一个点的时候，构成的图就是有向无环图。这里我们该怎么求有向图的强连通分量呢？如下图所示：