It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.

   它利用了有向圖的這樣一個(gè)性質(zhì)，一個(gè)圖和他的transpose graph(邊全部反向)具有相同的強(qiáng)連通分量！

算法偽代碼

Kosaraju's algorithm is simple and works as follows:

• Let G be a directed graph and S be an empty stack.
• While S does not contain all vertices:
  • Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
• Reverse the directions of all arcs to obtain the transpose graph.
• While S is nonempty:
  • Pop the top vertex v from S. Perform a depth-first search starting at v. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently,breadth-first search (BFS) can be used instead of depth-first search.

需要注意的是這里的第一遍BFS搜索的時(shí)候的入隊(duì)序列，Each time that depth-first search finishes expanding a vertex u, push u onto S.只有當(dāng)擴(kuò)展結(jié)束了此節(jié)點(diǎn)之后，此節(jié)點(diǎn)才會(huì)被push onto S.

算法思路：

1， 后序遍歷原圖，對(duì)每個(gè)訪問(wèn)到的節(jié)點(diǎn)標(biāo)記時(shí)間戳。

2， 按照時(shí)間戳的降序遍歷反向圖，得到的每個(gè)連通塊就是一個(gè)強(qiáng)連通分量。

證明是很簡(jiǎn)單的：

假設(shè)以上算法從u訪問(wèn)到了v，那么說(shuō)明反向圖有一條從u到v的邊，也就說(shuō)明了原圖中有一條從v到u的邊，又因?yàn)閡的標(biāo)號(hào)是大于v的，那么，u一定在v之前訪問(wèn)到（否則v的標(biāo)號(hào)將大于u），并且是從u訪問(wèn)到v了的（v到u也有一條路徑，否則就會(huì)從v訪問(wèn)到u）。

如果應(yīng)用我們第一個(gè)Tarjan算法的例子的話，第一遍DFS 得到的次序是 6 4 2 5 3 1

代碼

#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;
#define M 2000
bool vis[M];                 //遍歷數(shù)組
int post[M];                 //時(shí)間戳對(duì)應(yīng)的點(diǎn)
int timestamp;               //時(shí)間戳
int ComponetNumber=0;        //有向圖強(qiáng)連通分量個(gè)數(shù)
vector <int> Edge[M];        //鄰接表表示
vector <int> Opp[M];         //原圖的反圖
vector <int> Component[M];   //獲得強(qiáng)連通分量結(jié)果

void dfs(int u) {             //第一個(gè)dfs確定時(shí)間戳
    vis[u] = true;
    for(int i=0;i<Edge[u].size();i++) {
        if(vis[ Edge[u][i]])    continue;
        //cout<<Edge[u][i]<<endl;
        dfs(Edge[u][i]);
    }
    //cout<<"timestamp    "<<timestamp<<"       "<<u<<endl;   
    post[timestamp++] = u;
}

void dfs2(int u) {      //第二個(gè)反邊dfs確定連通塊
    vis[u] = true;
    Component[ComponetNumber].push_back(u);
    for(int i=0;i<Opp[u].size();i++)
    {
        int v = Opp[u][i];
        if(vis[v])  continue;
        dfs2(v);
    }
}

void Kosaraju(int n) {
    memset(vis,0,sizeof(vis));
    timestamp = 0;
    for(int i=0;i<n;i++) {
        if(vis[i])    continue;
        dfs(i);
    }
    memset(vis,0,sizeof(vis));
    ComponetNumber++;
    for(int i=n-1;i>=0;i--) {//按時(shí)間戳從大到小搜
        if(vis[post[i]])    continue;
        Component[ComponetNumber].clear();
        dfs2(post[i]);
        ComponetNumber++;
    }
    ComponetNumber--;      //最后我們把塊加了1。。所以要減掉
}
int main()
{
    Edge[0].push_back(1);Edge[0].push_back(2);
    Edge[1].push_back(3);
    Edge[2].push_back(3);Edge[2].push_back(4);
    Edge[3].push_back(0);Edge[3].push_back(5);
    Edge[4].push_back(5);

    Opp[0].push_back(3);
    Opp[1].push_back(0);
    Opp[2].push_back(0);
    Opp[3].push_back(1);Opp[3].push_back(2);
    Opp[4].push_back(2);
    Opp[5].push_back(3);Opp[6].push_back(4);
    int  N=6;
    Kosaraju(N);
    cout<<"ComponetNumber is "<<ComponetNumber<<endl;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<Component[i].size();j++)
            cout<<Component[i][j];
        cout<<endl;
    }
    return 0;
}

    此算法的時(shí)間復(fù)雜度當(dāng)然也是 O(M+N)（M條邊，N個(gè)點(diǎn)）與Tarjan算法相似。。但是在系數(shù)上不如Tarjan算法！在實(shí)際的測(cè)試中，Tarjan算法的運(yùn)行效率也比Kosaraju算法高30%左右。 

    當(dāng)然Kosaraju算法額外花費(fèi)的時(shí)間，也不是白費(fèi)的，它獲得了圖的一個(gè)拓?fù)湫再|(zhì)哦！！

    如果我們把求出來(lái)的每個(gè)強(qiáng)連通分量收縮成一個(gè)點(diǎn)，并且用求出每個(gè)強(qiáng)連通分量的順序來(lái)標(biāo)記收縮后的節(jié)點(diǎn)，那么這個(gè)順序其 實(shí)就是強(qiáng)連通分量收縮成點(diǎn)后形成的有向無(wú)環(huán)圖的拓?fù)湫蛄?/strong>。為什么呢？首先，應(yīng)該明確搜索后的圖一定是有向無(wú)環(huán)圖呢？廢話，如果還有環(huán)，那么環(huán)上的頂點(diǎn)對(duì)應(yīng) 的所有原來(lái)圖上的頂點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量，而不是構(gòu)成環(huán)上那么多點(diǎn)對(duì)應(yīng)的獨(dú)自的強(qiáng)連通分量了。然后就是為什么是拓?fù)湫蛄校覀冊(cè)诟倪M(jìn)分析的時(shí)候，不是先選 的樹(shù)不會(huì)連通到其他樹(shù)上（對(duì)于反圖GT來(lái)說(shuō)），也就是后選的樹(shù)沒(méi)有連通到先選的樹(shù)，也即先出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)只能指向后出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)。那么拓?fù)湫蛄胁皇抢硭?dāng)然的嗎？這就是Kosaraju算法的一個(gè)隱藏性質(zhì)。