首页 > 代码库 > poj1094
poj1094
受此文启发:
http://www.cnblogs.com/pushing-my-way/archive/2012/08/23/2652033.html
用链式表实现拓扑排序,我这里用的是栈,当然队列也是可以的。
#include<iostream> #include<cstring> #include<stack> using namespace std; int rudu[27],map[27][27],list[27]; int toposort(int n) { bool flag; int i,j,rudu1[27],temp1; stack<int>s1; memcpy(rudu1,rudu,sizeof(rudu1)); for(i=1;i<=n;i++) if(rudu1[i]==0) s1.push(i); i=0; flag=0; while(s1.size()!=0) { if(s1.size()>1) flag=1; temp1=s1.top(); s1.pop(); list[++i]=temp1; for(j=1;j<=n;j++) if(map[temp1][j]==1&&--rudu1[j]==0) s1.push(j); } if(i<n) return 1;//有环,无法形成n个元素的拓扑排序 else if(flag==1) return 2;//没有环,但入度为0的点不唯一,当前没有形成拓扑排序,但可以形成n个元素的拓扑排序 return 3;//已经形成n个元素的拓扑排序 } int main() { bool flag; char data[100]; int i,n,m,ans,j; while(scanf("%d%d",&n,&m)&&(n!=0||m!=0)) { flag=1; memset(rudu,0,sizeof(rudu)); memset(map,0,sizeof(map)); for(i=1;i<=m;i++) { scanf("%s",data); if(flag) { if(map[data[0]-64][data[2]-64]==0) { map[data[0]-64][data[2]-64]=1; rudu[data[2]-64]++; } ans=toposort(n); if(ans==1) { flag=0; printf("Inconsistency found after %d relations.\n",i); } else if(ans==3) { flag=0; printf("Sorted sequence determined after %d relations: ",i); for(j=1;j<=n;j++) printf("%c",list[j]+64); printf(".\n"); } } } if(flag) printf("Sorted sequence cannot be determined.\n"); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。