注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【拓扑排序】图论 拓扑排序模板 zz:吉大ACM模板库  

2012-01-18 17:47:11|  分类: ACM_图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

//edge[][] 为图的临界矩阵,count[ 0...i...n-1] :定点i的入度
//建图!!!!!
void TopoOrder(int n)
{
int i,top = -1;
for (i = 0;i < n;i ++) if(count[i] == 0)//下标模拟堆栈
{
count[i] = top;//count 保存i上一个的count为0 的点
top = i;//top 保存当前count为0的点,相当于链表链起来了
}

for (i = 0;i < n;i ++)
{
if(top == -1) //存在回路
{
printf("存在回路\n");
return ;
}
else
{
int j = top; top = count[top];
printf("%d",j);//输出拓扑顺序
for(int k = 0;k < n;k ++)
{
if(edge[j][k] && (--count[k]) == 0)
{
count[k] = top;
top = k;
}
}
}
}
}


  评论这张
 
阅读(327)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018