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;
}
}
}
//***************************************************************************//

最新文章

  1. C#创建委托实例
  2. 浅谈C#Socket
  3. 转:HIBERNATE一些_方法_@注解_代码示例---写的非常好
  4. fastjson生成和解析json数据,序列化和反序列化数据
  5. 一、Struts2的概述
  6. [课程相关]homework-01
  7. 处理 insert 字段内容包含 单引号 的问题
  8. linux调度器系列
  9. GDB 多进程调试
  10. android 工程里缺少 R.java 文件原因和解决方法
  11. easyDialog弹窗+zTree部门选择
  12. QGIS2.18.0的精简编译
  13. eMMC真能优化成UFS?谈谈手机闪存的文件系统
  14. JVM垃圾回收机制之对象回收算法
  15. MySQL中间件之ProxySQL(4):多层配置系统
  16. Golang 并发简介
  17. Django-rest-framework 接口实现 Serializer 使用
  18. python学习-Day1-接口测试
  19. topcoder srm 540 div1
  20. linux线程学习

热门文章

  1. IOS Animation-KeyPath值
  2. Java程序员的日常 —— 多进程开发IO阻塞问题
  3. WPF仿Win7便笺
  4. [javascript]模拟汉诺塔
  5. Sql Server 的本地时间和UTC时间
  6. Implementation Model Editor of AVEVA in OpenSceneGraph
  7. Android线程处理之Handler总结
  8. Office英语学习好帮手
  9. struts深入原理之RequestProcessor与xml
  10. 数据结构:C_顺序栈的实现