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.Sample Input
4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0Sample Output
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.这题太搞人了- -、给你一定的关系，问你是否出现环或是不唯一的情况，如果不出现的话，序列应该是多少。。如果是这样的话还不是很烦，可是它加上让你输出第几步的时候出现了这个情况- -。。无语啊。。这也得就每次输入的时候都得topo一下。当时想的有些混乱了。不过写出来感觉还好- -。。 View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <stack> 5 #include <algorithm> 6 using namespace std; 7 int map[30][30],degree[30]; 8 int rank[30],in[30]; 9 int n,m,cnt; 10 int flag;//flag标记环，唯一性 11 void Topo() 12 { 13 int i,j,num,x; 14 cnt=flag=0; 15 memcpy(in,degree,sizeof(degree)); 16 for(i=0;i<n;i++) 17 { 18 num=0; 19 for(j=0;j<n;j++) 20 if(in[j]==0) 21 { 22 num++; 23 x=j; 24 } 25 if(num==0) 26 { 27 flag=1;//有环 28 return ; 29 } 30 if(num>1) 31 flag=2;//不唯一 32 in[x]--; 33 rank[cnt++]=x; 34 for(j=0;j<n;j++) 35 if(map[x][j]) 36 in[j]--; 37 } 38 } 39 int main() 40 { 41 char s[5]; 42 int i,j; 43 while(scanf("%d%d",&n,&m)&&(n+m)) 44 { 45 memset(degree,0,sizeof(degree)); 46 memset(map,0,sizeof(map)); 47 flag=2; 48 for(i=1;i<=m;i++) 49 { 50 scanf("%s",s); 51 map[s[0]-'A'][s[2]-'A']=1; 52 degree[s[2]-'A']++; 53 if(flag==2) 54 Topo(); 55 if(flag==1) 56 { 57 printf("Inconsistency found after %d relations.\n",i); 58 flag=3; 59 } 60 else if(!flag) 61 { 62 printf("Sorted sequence determined after %d relations: ",i); 63 for(j=0;j<n;j++) 64 printf("%c",rank[j]+'A'); 65 printf(".\n"); 66 flag=3; 67 } 68 } 69 if(flag==2) 70 printf("Sorted sequence cannot be determined.\n"); 71 } 72 return 0; 73 }
转载于:https://www.cnblogs.com/wilsonjuxta/archive/2013/04/03/2997660.html
相关资源：JAVA上百实例源码以及开源项目