Sorting It All Out Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 29359 Accepted: 10170
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:Sample Input
4 6 A
Sample Output
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.
#include#include #include #include #include #include #include #define N 1009 using namespace std; char s[N]; int mp[27][27]; int q[N]; int deg[N]; int topo(int n) { int c=0,temp[27],m,loc,flag=1; for(int i=1;i<=n;i++) temp[i]=deg[i]; for(int i=1;i<=n;i++) { m=0; for(int j=1;j<=n;j++) if(temp[j]==0) { m++; loc=j; } if(m==0) return 0;//有環 if(m>1) flag=-1;//無環 q[c++]=loc; temp[loc]=-1; for(int j=1;j<=n;j++) if(mp[loc][j]==1) temp[j]--; } return flag; } int main() { int n,m; while(~scanf("%d %d",&m,&n)) { if(n==0 && m==0) break; memset(mp,0,sizeof mp); memset(deg,0,sizeof deg); int flag=0; for(int i=1;i<=n;i++) { scanf("%s",s); if(flag) continue; int a=s[0]-'A'+1; int b=s[2]-'A'+1; mp[a][b]=1; deg[b]++; int ans=topo(m); if(ans==0) { cout<<"Inconsistency found after "<