SCC重新建图

Tarjan或Kosaraju算法【对每个点归类belong】求出SCC之后,对num_scc个SCC重新建图,针对不同问题,考虑重边的问题。

 //**************************************重构图****************************************//
void init_rebuild(void)
{
rebuild_ALG->n=num_scc;
for(int i=;i<=num_scc;i++)
{
rebuild_ALG->vlist[i].vertex=i;
rebuild_ALG->vlist[i].firstedge=NULL; in_d[i]=;
out_d[i]=;
}
} void add_edge_To_ALG(int par,int son)
{
ENode *ptr=(ENode *)malloc(sizeof(ENode)); ptr->key=son;
ptr->next=rebuild_ALG->vlist[par].firstedge;
rebuild_ALG->vlist[par].firstedge=ptr;
} void rebuild_ALGraph(void)
{
int par,son;
int in_par_scc; //判断是否已在par的scc中
ENode *ptr=(ENode *)malloc(sizeof(ENode));
ENode *ep=(ENode *)malloc(sizeof(ENode)); for(int i=;i<ALG->n;i++)
{
par=i;
in_par_scc=;
ptr=ALG->vlist[par].firstedge;
while(ptr!=NULL)
{
son=ptr->key;
if(belong[par] != belong[son])
{
ep=rebuild_ALG->vlist[belong[par]].firstedge;//考虑重边问题
while(ep!=NULL)
{
if(ep->key == belong[son])
{
in_par_scc=;
break;
}
ep=ep->next;
}
if(!in_par_scc)
{
add_edge_To_ALG(belong[par],belong[son]);
in_d[belong[son]]++;
out_d[belong[par]]++;
}
}
ptr=ptr->next;
}
}
}
//***************************************************************************//
上一篇:LeetCode 376. Wiggle Subsequence 摆动子序列


下一篇:Comparable和Comparator接口的差异