时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

强连通分量(Strongly-Connected-Components)

图中的一个顶点与另一个顶点互相都有路径可以抵达，就说这两个顶点强连通。图中有多个顶点两两之间都强连通，则这多个顶点构成图的强连通分量。

朴素的想法是，假如从一个顶点A可以搜索到另一个顶点B，如果从B顶点再能搜索回A顶点的话，A、B就在一个强连通分量中。不过，这样每两个顶点要进行两次DFS，复杂度肯定会很高。这里可以引入转置图(将有向边的方向翻转)的性质。这样问题就转换成了，从A顶点搜索到B顶点，将图转置后，如果再A顶点还能搜索到B顶点，A、B顶点就在一个强连通分量中。用算法表述出来就是先从A顶点DFS，然后将图转置，再从A顶点DFS，两次DFS都能搜索到B顶点的话，B顶点就与A顶点在同一个强连通分量中。然而朴素想法只能想到这里了。

有多个算法被研究出来解决这个问题，下面先介绍Kosaraju算法。

• Kosaraju

Kosaraju算法使用了DFS改良的性质去解决问题，想法很有趣。Kosaraju算法现将图进行DFS改良，然后将图转置，再进行DFS。第二次DFS每个顶点能够搜索到的点就是一个强连通分量。算法正确性和说明如下。

通过DFS改良性质可以得出定理，一个强连通分量C如果有到达另一个强连通分量C’的路径，则C’比C先被搜索完，这个定理很明显，如果C中有路径到C’，那么根据DFS改良性质一定会先搜索到C，再搜索完C’，再搜索完C。将这个定理做定理1。

定理1：一个强连通分量C如果有到达另一个强连通分量C’的路径，则C’比C先被搜索完。

定理1还可以再进行推论，如果一个强连通分量C有到达另一个强连通分量C’的路径，则将图转置后，C比C’先被搜索完，这个推论也很明显，将图转置后，不存在C到C’的路径，存在C’到C的路径，而仍是先搜索C再搜索C‘，所以C比C‘先被搜索完，这个推论作为推论1。

推论1：如果一个强连通分量C有到达另一个强连通分量C’的路径，则将图转置后，C比C’先被搜索完。

以下为用结构归纳法对算法正确性进行证明。

命题：第二次DFS每个顶点能够搜索到的点就是一个强连通分量。

假设：n代表图中有多少个强连通分量。 

证明：如果n=1，则第二次DFS就是搜索一遍所有顶点，命题得证。现在假设n=k时，命题成立。现证明n=k+1时，是否成立。假设搜索到第k+1个强连通分量的第一个顶点为u，u肯定能搜索到所有k+1个强连通分量的顶点。并且根据推论1，此时被转置后的图，所有从第k+1个强连通分量能到达的其他强连通分量都已经被搜索过了。所以u只能搜索到所有第k+1个强连通分量的顶点，即第二次DFS每个顶点只能够搜索到包含此顶点的强连通分量中的顶点，命题得证。

伪代码：
KOSARAJU-STRONGLY-CONNECTED-COMPONENTS(g)
  let visited be new Array
  let stack be new Stack
  for v equal to every vertex in g
    if visited[v] == false
      DFS-IMPROVE(v,visited,stack)
  end
  let gt = transpose of g
  for v equal to every vertex in g
    visited[v] = false
  end
  while stack.empty() == false
    vertex v = stack.top()
    stack.pop()
    if visited[v] == false
      DFS(v,visited)
      print '\n Found a Strongly Connected Components \n'
  end
 
DFS(v,visited)
  visited[v] = true
  print v
  for i equal to every vertex adjacent to v
    if visited[i] == false
      DFS(i,visited,stack)
  end

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

Kosaraju算法需要进行两次DFS，那么可不可以只进行一次DFS，边遍历边找强连通分量？Tarjan就是这样的算法。

• Tarjan

同样，还是要基于DFS搜索性质来思考问题。DFS创建出的深度优先搜索树会先被访问根节点再被访问子孙节点。什么时候会出现强连通分量？只有子孙节点有连通祖先节点的边的时候。如果从某个节点，其子孙节点都只有指向自己子孙节点的边的时候，这是明显没有构成强连通分量的。那么，出现了子孙节点指向其祖先节点的时候，从被指向的祖先节点一直搜索到指向的子孙节点所经过所有顶点就构成了一个强连通分量。如果出现了多个子孙节点都指向了祖先节点怎么办？最早被指向、访问的祖先节点到最晚指向、访问的子孙节点构成了“最大“的强连通分量，这才是想要找的强连通分量。如果遇到了一个指向祖先节点的子孙节点，就算构成一个强连通分量，会导致找到多个互相嵌套的强连通分量。那么，要记录访问顺序就要为每个节点设置一个被访问顺序的编号，让属于同一个强连通分量的顶点编号一致。上面讨论的是构成了一个强连通分量怎么处理，如果没有多个节点构成的强连通分量怎么处理？在搜索节点之前，为这个节点默认设置上被访问的顺序编号，这样如果没有搜索到多个节点构成的强连通分量，每个节点就是自己的强连通分量。

算法表述为，从某个节点开始搜索，默认设置自己为一个强连通分量。只要节点有子孙节点，就要等待子孙节点都搜索完，再更新自己强连通分量信息。只要节点有指向祖先节点，也要更新自己的强连通分量。判断子孙节点构成的强连通分量”大“还是自己构成的强连通分量”大“，自己属于最”大“的强连通分量。也就是说，算法找出了所有顶点的所属的最“大”强连通分量。

数组disc表示顶点被访问顺序的编号，数组low表示顶点所在的强连通分量编号。最后当顶点在disc和low中编号一致时，代表顶点是所在强连通分量中第一个被搜索到的顶点。此时，输出所在的强连通分量所包括的顶点。