首页 > 代码库 > POJ1094拓扑排序
POJ1094拓扑排序
每次输入的时候 进行一次 拓扑排序。 拓扑排序时,每次查找入度为零的点只有一个,则此解为确定解。若找到确定解之后出现环(坑),继续输入,不管它。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int main(){ //freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n,m;char str[100]; int vis[100];int G[100][100]; int in[100],in1[100]; int topo[100]; while(cin>>n>>m,n||m){ memset(G,0,sizeof(G)); memset(in,0,sizeof(in)); int flag=1;int ans=0;int sign=0;int sum=0;int pos; for(int t=0;t<m;t++){ cin>>str;int a=str[0]-‘A‘;int b=str[2]-‘A‘; if(!G[a][b]) { G[a][b]=1;in[b]++; } for(int i=0;i<n;i++) in1[i]=in[i]; int sum=0; memset(vis,0,sizeof(vis)); for(int i=0;i<n&&flag;i++){ int sign1;bool k=false; for(int j=0;j<n;j++){ // cout<<j<<" "<<vis[j]<<" "<<in1[j]<<endl; if(in1[j]==0&&!vis[j]){ sign1=j;sum++;k=true; } } // cout<<i<<" "<<k<<endl; vis[sign1]=1; if(!ans) topo[i]=sign1; if(!k){ flag=0;sign=t+1; } for(int j=0;j<n;j++){ if(!vis[j]) if(G[sign1][j]) in1[j]--; } pos=i; } if(pos==n-1&&sum==n&&!ans){ ans=t+1; } } if(ans){ printf("Sorted sequence determined after %d relations: ",ans); for(int i=0;i<n;i++){ char c=topo[i]+‘A‘; cout<<c; } cout<<‘.‘<<endl; } else{ if(sign){ printf("Inconsistency found after %d relations.\n",sign); } else printf("Sorted sequence cannot be determined.\n"); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。