Tarjan或Kosaraju算法【对每个点归类belong】求出SCC之后，对num_scc个SCC重新建图，针对不同问题，考虑重边的问题。
1 //**************************************重构图****************************************// 2 void init_rebuild(void) 3 { 4 rebuild_ALG->n=num_scc; 5 for(int i=1;i<=num_scc;i++) 6 { 7 rebuild_ALG->vlist[i].vertex=i; 8 rebuild_ALG->vlist[i].firstedge=NULL; 9 10 in_d[i]=0; 11 out_d[i]=0; 12 } 13 } 14 15 void add_edge_To_ALG(int par,int son) 16 { 17 ENode *ptr=(ENode *)malloc(sizeof(ENode)); 18 19 ptr->key=son; 20 ptr->next=rebuild_ALG->vlist[par].firstedge; 21 rebuild_ALG->vlist[par].firstedge=ptr; 22 } 23 24 void rebuild_ALGraph(void) 25 { 26 int par,son; 27 int in_par_scc; //判断是否已在par的scc中 28 ENode *ptr=(ENode *)malloc(sizeof(ENode)); 29 ENode *ep=(ENode *)malloc(sizeof(ENode)); 30 31 for(int i=0;i<ALG->n;i++) 32 { 33 par=i; 34 in_par_scc=0; 35 ptr=ALG->vlist[par].firstedge; 36 while(ptr!=NULL) 37 { 38 son=ptr->key; 39 if(belong[par] != belong[son]) 40 { 41 ep=rebuild_ALG->vlist[belong[par]].firstedge;//考虑重边问题 42 while(ep!=NULL) 43 { 44 if(ep->key == belong[son]) 45 { 46 in_par_scc=1; 47 break; 48 } 49 ep=ep->next; 50 } 51 if(!in_par_scc) 52 { 53 add_edge_To_ALG(belong[par],belong[son]); 54 in_d[belong[son]]++; 55 out_d[belong[par]]++; 56 } 57 } 58 ptr=ptr->next; 59 } 60 } 61 } 62 //***************************************************************************//