有向圖強連通分量：
在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

( 一 ) Kosaraju 算法

Kosaraju的主要步驟：

• 1.對G求解Reverse Post-Order，即上文中的”偽拓撲排序“
• 2.對G進行轉(zhuǎn)置得到G(R)
• 3.按照第一步得到的集合中頂點出現(xiàn)的順序，對G(R)調(diào)用DFS得到若干顆搜索樹,每一顆搜索樹就代表了一個強連通分量

復雜度分析：
　根據(jù)上面總結(jié)的Kosaraju算法關(guān)鍵步驟，不難得出，該算法需要對圖進行兩次DFS，以及一次圖的轉(zhuǎn)置。所以時間復雜度為O(V+E)。

下面對這個算法的正確性進行證明：
證明的目標:就是最后一步 --- 每一顆搜索樹代表的就是一個強連通分量
證明：
設(shè)在圖GR中，調(diào)用DFS(s)能夠到達頂點v，那么頂點s和v是強連通的。
兩個頂點如果是強連通的，那么彼此之間都有一條路徑可達，因為DFS(s)能夠達到頂點v，因此從s到v的路徑必然存在?，F(xiàn)在關(guān)鍵就是需要證明在GR中從v到s也是存在一條路徑的，也就是要證明在G中存在s到v的一條路徑。
而之所以DFS(s)能夠在DFS(v)之前被調(diào)用，是因為在對G獲取ReversePost-Order序列時，s出現(xiàn)在v之前，這也就意味著，v是在s之前加入該序列的(因為該序列使用棧作為數(shù)據(jù)結(jié)構(gòu)，先加入的反而會在序列的后面)。因此根據(jù)DFS調(diào)用的遞歸性質(zhì)，DFS(v)應該在DFS(s)之前返回，而有兩種情形滿足該條件：

• DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END
• DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END

是因為而根據(jù)目前的已知條件，GR中存在一條s到v的路徑，即意味著G中存在一條v到s的路徑，而在第一種情形下，調(diào)用DFS(v)卻沒能在它返回前遞歸調(diào)用DFS(s)，這是和G中存在v到s的路徑相矛盾的，因此不可取。故情形二為唯一符合邏輯的調(diào)用過程。而根據(jù)DFS(s) START -> DFS(v) START可以推導出從s到v存在一條路徑。
所以從s到v以及v到s都有路徑可達，證明完畢。

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=10010;
vector<int> graph[MAXN];
vector<int> reveGraph[MAXN];
stack<int> posOrder;
int vis[MAXN];
int component[MAXN];//求出節(jié)點在那個連通分量
vector<int> cc[MAXN];//一個個獨立的連通分量
int cnt;//連通分量數(shù)
void DFS1(int u)//獲得原圖的ReversePostOrder
{
    vis[u]=1;
    for(int i=0;i<graph[u].size();i++)
    {
        int v=graph[u][i];
        if(vis[v]==0) DFS1(v);
    }
    posOrder.push(u);
}
void DFS2(int u)//在轉(zhuǎn)置圖進行DFS
{
    component[u]=cnt;
    cc[cnt].push_back(u);
    vis[u]=1;
    for(int i=0;i<reveGraph[u].size();i++)
    {
        int v=reveGraph[u][i];
        if(vis[v]==0) DFS2(v);
    }
}
void Kosaraju(int n)
{
    memset(vis,0,sizeof(vis));
    while(!posOrder.empty()) posOrder.pop();
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            DFS1(i);
        }
    }
    memset(reveGraph,0,sizeof(reveGraph));
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<graph[i].size();j++)
        {
            int v=graph[i][j];
            reveGraph[v].push_back(i);
        }
    }
    cnt=0;
    memset(vis,0,sizeof(vis));
    memset(cc,0,sizeof(cc));
    while(!posOrder.empty())
    {
        int u=posOrder.top();
        posOrder.pop();
        if(vis[u]==0)
        {
            DFS2(u);
            cnt++;
        }
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<cc[i].size();j++)
        {
            printf("%d ",cc[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        memset(graph,0,sizeof(graph));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
        }
        Kosaraju(n);
    }
}

( 二 ) Tarjan 算法

ps:劉汝佳訓練指南講得很清楚了,看書去

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int MAXN=10010;
const int MAXE=100010;
struct Node
{
    int to,next;
};
Node edge[MAXE];
int cnt,head[MAXN];
stack<int> st;
int lowlink[MAXN],dfn[MAXN],clocks;
int sccno[MAXN],scc_cnt;
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void DFS(int u)
{
    lowlink[u]=dfn[u]=++clocks;
    st.push(u);
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dfn[v]==0)
        {
            DFS(v);
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }
        else if(sccno[v]==0)
        {
            lowlink[u]=min(lowlink[u],dfn[v]);
        }
    }
    if(lowlink[u]==dfn[u])
    {
        scc_cnt++;
        while(true)
        {
            int x=st.top();
            st.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
}
void find_scc(int n)
{
    memset(dfn,0,sizeof(dfn));
    memset(sccno,0,sizeof(sccno));
    clocks=scc_cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            DFS(i);
        }
    }
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addEdge(a,b);
        }
        find_scc(n);
    }
}