首先來看幾個概念:     

在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(strongly connected)。

如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。

非強連通圖有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

任意有向圖都可以分解成若干不想交的強連通分量,這就是強連通量的分解.把分解后的強連通分量縮成一個頂點,就得到了一個DAG(有向無環圖).

參考博客:http://blog.csdn.net/justlovetao/article/details/6673602

Tarjan算法

其實，tarjan算法的基礎是DFS。我們準備兩個數組Low和Dfn。Low數組是一個標記數組，記錄該點所在的強連通子圖所在搜索子樹的根節點的Dfn值（很繞嘴，往下看你就會明白），Dfn數組記錄搜索到該點的時間，也就是第幾個搜索這個點的。根據以下幾條規則，經過搜索遍歷該圖（無需回溯）和對棧的操作，我們就可以得到該有向圖的強連通分量。 

1、數組的初始化：當首次搜索到點p時，Dfn與Low數組的值都為到該點的時間。

2、堆棧：每搜索到一個點，將它壓入棧頂。

3、當點p有與點p’相連時，如果此時（時間為dfn[p]時）p’不在棧中，p的low值為兩點的low值中較小的一個。

4、當點p有與點p’相連時，如果此時（時間為dfn[p]時）p’在棧中，p的low值為p的low值和p’的dfn值中較小的一個。

5、每當搜索到一個點經過以上操作后（也就是子樹已經全部遍歷）的low值等于dfn值，則將它以及在它之上的元素彈出棧。這些出棧的元素組成一個強連通分量。

6、繼續搜索（或許會更換搜索的起點，因為整個有向圖可能分為兩個不連通的部分），直到所有點被遍歷。

      由于每個頂點只訪問過一次，每條邊也只訪問過一次，我們就可以在O（n+m）的時間內求出有向圖的強連通分量。但是，這么做的原因是什么呢？

      Tarjan算法的操作原理如下：

1、Tarjan算法基于定理：在任何深度優先搜索中，同一強連通分量內的所有頂點均在同一棵深度優先搜索樹中。也就是說，強連通分量一定是有向圖的某個深搜樹子樹。

2、可以證明，當一個點既是強連通子圖Ⅰ中的點，又是強連通子圖Ⅱ中的點，則它是強連通子圖Ⅰ∪Ⅱ中的點。

3、這樣，我們用low值記錄該點所在強連通子圖對應的搜索子樹的根節點的Dfn值。注意，該子樹中的元素在棧中一定是相鄰的，且根節點在棧中一定位于所有子樹元素的最下方。

4、強連通分量是由若干個環組成的。所以，當有環形成時（也就是搜索的下一個點已在棧中），我們將這一條路徑的low值統一，即這條路徑上的點屬于同一個強連通分量。

5、如果遍歷完整個搜索樹后某個點的dfn值等于low值，則它是該搜索子樹的根。這時，它以上（包括它自己）一直到棧頂的所有元素組成一個強連通分量。

Kosaraju算法

算法步驟調用DFS(G), 計算出每個結點的f[u]計算GT調用DFS(GT), 在主循環中按照f[u]遞減的順序執行DFS-VISIT, 則得到的每個DFS樹恰好對應于一個SCC運行時間：O(n+m)                            

SCC的f性質

當按照f值排序以后, 第二次DFS是按照SCC的拓撲順序進行(以后所指d[u]和f[u]都是第一次DFS所得到的值)記d(C)和f(C)分別表示集合C所有元素的最早發現時間和最晚完成時間, 有如下定理:定理: 對于兩個SCC C和C’, 如果C到C’有邊, 則f(C)>f(C’)情況一: d(C) < d(C’), 考慮C中第一個被發現的點x, 則C’全為白色, 而C到C’有邊, 故x到C’中每個點都有白色路徑. 這樣, C和C’全是x的后代, 因此f(C) > f(C’)情況二: d(C) > d(C’). 由于從C’不可到達C, 因此必須等C’全部訪問完畢才能訪問C. 因此f(C) > f(C’)推論:對于兩個SCC C和C’, 如果在GT中C到C’有邊, 則f(C)

以HDU1269為例來看這兩種算法的代碼,具體解釋見注釋.

/*有向圖強連通分量*///Tarjan算法const int maxn=200010;//點的個數const int maxm=500010;//邊的個數struct edge{    int to,next;}eg[Maxm];int head[Maxn],tot;int low[Maxn],dfn[Maxn],Stack[Maxn],Belong[Maxn];/*Belong[Maxn]各頂點屬于哪個強連通分量Instack[Maxn]標記是否在stack中dfn[Maxn]節點u搜索的序號(時間戳)low[Maxn]u或u的子樹能夠追溯到的最早的棧中節點的序號(時間戳)Index序號(時間戳)scc強連通分量的個數*/int Index,top,scc;bool Instack[Maxn];int num[Maxn];//各個強連通分量包含點的個數，數組編號1~scc,num數組不一定需要，結合實際情況void addedge(int u,int v){    eg[tot].to=v;    eg[tot].next=head[u];    head[u]=tot++;}void Tarjan(int u){    int v;    low[u]=dfn[u]=++Index;    Stack[top++]=u;    Instack[u]=true;    for(int i=head[u];i!=-1;i=eg[i].next)    {        int v=eg[i].to;        //cout<<u<<"*"<<v<<" ";        if(!dfn[v])        {            Tarjan(v);                low[u]=min(low[u],low[v]);        }        else if(Instack[v])            low[u]=min(dfn[v],low[u]);    }    if(low[u]==dfn[u])    {        scc++;        do        {            v=Stack[--top];            Instack[v]=false;            Belong[v]=scc;        }        while(v!=u);    }}void solve(int N){    memset(dfn,0,sizeof(dfn));    memset(Instack,0,sizeof(dfn));    Index=scc=top=0;    for(int i=1;i<=N;i++)    {        if(dfn[i]==0)            Tarjan(i);    }}void init(){    tot=0;    memset(head,-1,sizeof(head));}int main(){   int n,m;   while(~scanf("%d%d",&n,&m))   {       init();       if(n==0&&m==0)        break;        int u,v;       for(int i=0;i<m;i++)       {           scanf("%d%d",&u,&v);           addedge(u,v);       }       solve(n);//       for(int i=1;i<=n;i++)          //PRintf("%d*%d ",Belong[i],num[i]);       //cout<<scc<<endl;       if(scc==1)        printf("Yes/n");       else        printf("No/n");   }}
const int maxn=200010;//點的個數const int maxm=500010;//邊的個數int low[maxn],dfn[maxn];vector<int>G[maxn];int sccno[maxn];int scc,Index;stack<int>s;void dfs(int u){    dfn[u]=low[u]=++Index;    s.push(u);    for(int i=0;i<G[u].size();i++)    {        int v=G[u][i];        if(!dfn[v])        {            dfs(v);            low[u]=min(low[v],low[u]);        }        else if(!sccno[v])            low[u]=min(low[u],dfn[v]);    }    if(low[u]==dfn[u])    {        scc++;        for(;;)        {            int x=s.top();            s.pop();            sccno[x]=scc;            if(x==u)                break;        }    }}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        scc=Index=0;        if(n==0&&m==0)            break;        memset(dfn,0,sizeof(dfn));        memset(sccno,0,sizeof(sccno));        memset(low,0,sizeof(low));        for(int i=0;i<=n;i++)            G[i].clear();        while(!s.empty())            s.pop();        int u,v;        for(int i=0;i<m;i++)        {            scanf("%d%d",&u,&v);            G[u].push_back(v);        }        for(int i=1;i<=n;i++)        {            if(!dfn[i])                dfs(i);        }//        cout<<scc<<"*********"<<endl;//        for(int i=0;i<=n;i++)//            cout<<sccno[i]<<"***"<<endl;        if(scc==1)            printf("Yes/n");        else            printf("No/n");    }}
Kosaraju算法:
/*有向圖強連通分量*/#include<stdio.h>#include<algorithm>#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<map>#include<set>#include<stack>#include<stdlib.h>using namespace std;typedef long long LL;const int maxn=200010;//點的個數const int maxm=500010;//邊的個數vector<int>G[maxn],G2[maxn];vector<int>s;int vis[maxn],sccno[maxn],scc;void dfs1(int u)//第一次dfs,為逆序遍歷排序{    if(vis[u])        return;    vis[u]=1;    for(int i=0;i<G[u].size();i++)    {        int v=G[u][i];        dfs1(v);    }    s.push_back(u);}void dfs2(int u)//第二次dfs{    if(sccno[u])        return;    sccno[u]=scc;//每個點屬于哪一個強連通分量    for(int i=0;i<G2[u].size();i++)    {        dfs2(G2[u][i]);    }}void find_scc(int n){    scc=0;    s.clear();    memset(sccno,0,sizeof(sccno));    memset(vis,0,sizeof(vis));    for(int i=1;i<=n;i++)        dfs1(i);    for(int i=s.size()-1;i>=0;i--)    {        if(!sccno[s[i]])        {            scc++;//強連通分量的個數            dfs2(s[i]);        }    }}int main(){    int n,m,u,v;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0)            break;        for(int i=0;i<=n;i++)        {            G[i].clear();            G2[i].clear();        }        for(int i=1;i<=m;i++)        {            scanf("%d%d",&u,&v);            G[u].push_back(v);//圖的鄰接表表示            G2[v].push_back(u);//反向后的圖        }        find_scc(n);//        for(int i=0;i<=n;i++)//            cout<<sccno[i]<<" "<<endl;//        printf("%d****",scc);         if(scc==1)            printf("Yes/n");         else            printf("No/n");    }}
struct edge{    int to,next;}eg1[maxm],eg2[maxm];int head1[maxn],head2[maxn];bool mark1[maxn],mark2[maxn];int tot1,tot2,cnt1,cnt2;int st[maxn];//對原圖進行dfs，點的結束時間從小到大排序int Belong[maxn];//每個點屬于哪個連通分量0~cnt2-1int num;//中間變量,用來數某個連通分量中點的個數int setnum[maxn];//強連通分量中點的個數,編號(0~cnt2-1)void addedge(int u,int v){    eg1[tot1].to=v;    eg1[tot1].next=head1[u];    head1[u]=tot1++;    eg2[tot2].to=u;    eg2[tot2].next=head2[v];    head2[v]=tot2++;}void dfs1(int u){    mark1[u]=true;    for(int i=head1[u];i!=-1;i=eg1[i].next)    {        int v=eg1[i].to;        if(mark1[v]==0)            dfs1(v);    }    st[cnt1++]=u;}void dfs2(int u){    mark2[u]=true;    num++;    Belong[u]=cnt2;    for(int i=head2[u];i!=-1;i=eg2[i].next)    {        int v=eg2[i].to;        if(!mark2[v])            dfs2(v);    }}void solve(int n){    memset(mark1,false,sizeof(mark1));    memset(mark2,false,sizeof(mark2));    cnt1=cnt2=0;    for(int i=1;i<=n;i++)    {        if(!mark1[i])            dfs1(i);    }    for(int i=cnt1-1;i>=0;i--)    {        if(!mark2[st[i]])        {            num=0;            dfs2(st[i]);            setnum[cnt2++]=num;        }    }}int main(){   int n,m;   while(~scanf("%d%d",&n,&m))   {       memset(st,0,sizeof(st));       memset(setnum,0,sizeof(setnum));       memset(Belong,0,sizeof(Belong));       memset(head1,-1,sizeof(head1));       memset(head2,-1,sizeof(head2));       if(n==0&&m==0)        break;        int u,v;       for(int i=0;i<m;i++)       {           scanf("%d%d",&u,&v);           addedge(u,v);       }       solve(n);//       int ans=0;//       for(int i=0;i<=n;i++)//       {////           if(Belong[i]==1)////            ans++;//           printf("%d*%d ",Belong[i],setnum[i]);//       }       //cout<<cnt2<<"***"<<endl;       if(setnum[0]==n)        printf("Yes/n");       else        printf("No/n");   }}