Sorting It All Out

全栈程序员-站长 • 2021年9月1日下午10:00 • 未分类 • 阅读 59

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 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<vector>
10 using namespace std;
11 const int ms=26;
12 int n,m;
13 bool appear[ms];
14 char output[ms+1];
15 int cnt[ms];
16 int tmp[ms];
17 vector<vector<char> > v;
18 int topo_sort(int s)
19 {
20     int i,j,k,flag=1;
21     int total=0,r=0;
22     for(i=0;i<n;i++)
23         tmp[i]=cnt[i];
24     while(s--)
25     {
26         total=0;
27         for(i=0;i<n;i++)
28             if(appear[i]&&tmp[i]==0)
29             {
30                 j=i;
31                 total++;
32             }
33         if(total>=1)
34         {
35             if(total>1)
36                 flag=0;
37             for(i=0;i<v[j].size();i++)
38                 tmp[v[j][i]]--;
39             tmp[j]=-1;
40             output[r++]=j+'A';
41             output[r]=0;
42         }
43         else
44             return -1;
45     }
46     if(flag)
47         return r;
48     return 0;
49 }
50 int main()
51 {
52     int i,j,k,judge,det;
53     char str[4];
54     while(scanf("%d%d",&n,&m)==2&&(n+m))
55     {
56         judge=0;
57         det=0;
58         int sum=0;
59         v.clear();v.resize(n);
60         memset(cnt,0,sizeof(cnt));
61         memset(appear,false,sizeof(appear));
62         for(i=1;i<=m;i++)
63         {
64             scanf("%s",str);
65             cnt[str[2]-'A']++;
66             v[str[0]-'A'].push_back(str[2]-'A');
67             if(!appear[str[0]-'A'])
68             {
69                 sum++;
70                 appear[str[0]-'A']=1;
71             }
72             if(!appear[str[2]-'A'])
73             {
74                 sum++;
75                 appear[str[2]-'A']=1;
76             }
77             if(judge==0)
78             {
79                 det=topo_sort(sum);
80                 if(det==-1)
81                 {
82                     judge=-1;k=i;
83                 }
84                 else if(det==n)
85                 {
86                     judge=1;
87                     k=i;
88                 }
89             }
90         }
91         if(judge==-1)
92             printf("Inconsistency found after %d relations.\n",k);
93         else if(judge==0)
94             printf("Sorted sequence cannot be determined.\n");
95         else
96             printf("Sorted sequence determined after %d relations: %s.\n",k,output);
97     }
98     return 0;
99 }