首页 > 代码库 > POJ1094[有向环 拓扑排序]
POJ1094[有向环 拓扑排序]
Sorting It All Out
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 33184 | Accepted: 11545 |
Description
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sample Input
4 6A<BA<CB<CC<DB<DA<B3 2A<BB<A26 1A<Z0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD.Inconsistency found after 2 relations.Sorted sequence cannot be determined.
Source
East Central North America 2001
因为要求几个relation，所以没加一个进行一次topoSort
一旦遇到有环或者唯一有序就sign＝1，后面的关系一定要读完(后果自负)，如果最后sign==0说明没确定顺序
要打印方案，可以用char topo[]来保存，然而输出topo[]比一个个输出慢了16MS，并且还忘初始化了WA好几次
//// main.cpp// poj1094//// Created by Candy on 9/11/16.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=30;int n,m,ind[N],ch[N][N];char tmp[5],topo[N];int q[N];int topoSort(){ int flag=2;//only sorted int indt[N]; for(int i=1;i<=n;i++) indt[i]=ind[i]; for(int i=1;i<=n;i++){//printf("%d %d %d \n",i,ind[i],ch[i][0]); int zero=0,u=0; for(int j=1;j<=n;j++) if(indt[j]==0) zero++,u=j; if(zero==0) return 1;//circle if(zero>1) flag=3;//no sorted indt[u]--; topo[i-1]=(char)u+‘A‘-1; q[i-1]=u; for(int j=1;j<=ch[u][0];j++) indt[ch[u][j]]--; } return flag;}int main(int argc, const char * argv[]) { while(cin>>n>>m){ if(n==0&&m==0) break; memset(ch,0,sizeof(ch)); memset(ind,0,sizeof(ind)); memset(topo,0,sizeof(topo)); int sign=0; for(int i=1;i<=m;i++){ scanf("%s",tmp); if(sign) continue; int x=tmp[0]-‘A‘+1,y=tmp[2]-‘A‘+1; ind[y]++; ch[x][++ch[x][0]]=y; int flag=topoSort(); if(flag==1){sign=1;printf("Inconsistency found after %d relations.\n",i);} if(flag==2){ sign=1;printf("Sorted sequence determined after %d relations: %s.\n",i,topo);// printf("Sorted sequence determined after %d relations: ",i);// for(int j=0;j<n;j++)// printf("%c",q[j]+‘A‘-1);// printf(".\n");// sign=1; } } if(!sign) printf("Sorted sequence cannot be determined.\n"); } return 0;}
POJ1094[有向环 拓扑排序]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。