Kosaraju算法求有向圖的極大連通子圖。算法首先對逆圖做后序遍歷，求出后序編碼。隨后從右到左掃描編碼，對于每一個未標記所屬分量編號的節點，以它為根做一次DFS，標記沿途所遇到的所有節點為同一個強連通分量。
   算法正確性的證明基于：任意兩點s,t在原圖中屬于強聯通分量的話，當且僅當在逆圖中兩者也屬于同一強連通分量

#define MAXV 100000
 static int postR[MAXV],post[MAXV];
 static int cnt0,cnt1;

typedef struct LinkNod *Link;
struct LinkNod{
     int dest;
     Link next;
};

typedef struct GraphNod *Graph;
struct GraphNod{
     Link v[MAXV];
     int vnum;
     int id[MAXV];  // 分量標號 
};

int IsScc(Graph g,int s,int t){
    return g->id[s] == g->id[t];
}

void DFS(Graph g,int w){
     g->id[w] = cnt1;
     for( Link pos = g->v[w]; pos!=NULL; pos=pos->next ) if( g->id[ pos->dest ] == -1 ) DFS(g,pos->dest);
     post[cnt0++] = w; // 后序編碼 
}

Graph MakeGraphR(Graph g){
     Link pos;
     Link tmpNod;
     Graph r = (Graph)malloc(sizeof(struct GraphNod));
     r->vnum = g->vnum;
     for(int i=0;i<r->vnum;i++) r->v[i] = NULL;
     for(int i=0;i<g->vnum;i++){
        pos = g->v[i];
while(pos){  
     tmpNod = (Link)malloc(sizeof(struct LinkNod));
     tmpNod->dest = i; tmpNod->next = r->v[pos->dest]; 
     r->v[ pos->dest ] = tmpNod;
     pos=pos->next; 
  }
     }
     return r;
}

int FindScc(Graph g){
   Graph r = MakeGraphR(g);
   memset(r->id,-1,sizeof(r->id));
   cnt0 = cnt1 =0;
   for( int i=0;i<r->vnum;i++ ) if( r->id[i] == -1 ) DFS(r,i);
   for(int i=0;i<g->vnum;i++) postR[i] = post[i];
   memset(g->id,-1,sizeof(g->id)); 
   cnt0 = cnt1 =0;
   for( int i=g->vnum-1;i>-1;i-- ) if( g->id[ postR[i] ] == -1 ){  DFS(g,postR[i]); cnt1++;  }
   printf("分量陣:\n");
   for( int i=0;i<g->vnum;i++ ) printf("%d: %d\n",i,g->id[i]);
   return cnt1;  // 分量數 
}