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