关于我们

质量为本、客户为根、勇于拼搏、务实创新

< 返回

ZOJ1060

发布时间:2022-07-27 13:56:10
Sorting It All Out

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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. 

ZOJ1060

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 <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int obj[26];    //obj[i]表示第i+1个字母出现在"<"右端的次数,用于处理关系的方向性
 6 int temp[26];    //temp为obj的拷贝,用于拓扑排序时进行修改
 7 char relation[3], seq[26]; //relation用于读入对象间关系,seq用于存储得到的序列
 8 bool alpha[26];    //alpha用于记录对象是否已经检查
 9 int n, m;
10 vector< vector<char> > v;    //使用STL的成员vector来存储节点
11 
12 //拓扑排序,返回拓扑排序后得到的序列中元素的个数;若发现矛盾则返回-1,无法判断则返回0
13 int toposort( int s )
14 {
15     int i, j;    //j表示当前已读入的未出现在"<"右端的对象
16     int r, cnt;    //cnt表示这些对象的个数;r表示得到序列中元素的个数
17     bool flag;    //flag为标志变量,表示拓扑排序结束后是否可以得到序列
18     r = 0,  cnt = 0;
19     for( i = 0; i < n; i++ )  temp[i] = obj[i];
20     flag = 1;
21     while( s-- )
22     {
23         cnt = 0;
24         for( i = 0; i < n; i++ )
25         {
26             if( temp[i] == 0 )
27                 j = i,  cnt++;
28         }
29         if( cnt>=1 )
30         {
31             //cnt=1表示仅一个对象出现在"<"右端,则该对象必然处于序列最右端
32             if( cnt>1 )  flag = 0;
33             for( i=0; i<v[j].size( ); i++ )
34                 temp[ v[j][i] ]--; //处理完毕后剔除
35             seq[r++] = j + 'A';
36             temp[j] = -1;  seq[r] = 0;
37         }
38         else if( cnt == 0 )    //cnt==0表示当前已读入的对象均出现在"<"右端一次以上
39             return -1;        //则必然存在环
40     }
41     if( flag )  return r;
42     else  return 0;
43 }
44 
45 int main( )
46 {
47     int i, t, k;    //k用于记录关系矛盾或可以得到序列时已处理的关系个数
48     int count;    //count用于记录读入的对象个数
49     int determined; //determined用于标记是否可以得到序列
50                     //-1表示关系矛盾、0表示无法得到序列、1表示可以得到序列
51     while( scanf( "%d %d", &n, &m ) != EOF && n != 0 && m != 0 )
52     {
53         memset( obj, 0, sizeof( obj ));    //初始化
54         memset( alpha, false, sizeof( alpha ));
55         //删除vector中的元素,并重新调整大小
56         v.clear(  );  v.resize( n );
57         count = 0;  determined = 0;
58         for( i=0; i<m; i++ )
59         {
60             scanf( "%s", relation );    //读入数据
61             obj[ relation[2]-'A' ]++;
62             v[ relation[0]-'A' ].push_back( relation[2]-'A' );
63             //记录读入的对象个数
64             if( !alpha[ relation[0]-'A' ] )
65             {
66                 count++;  alpha[ relation[0]-'A' ] = true;
67             }
68             if( !alpha[ relation[2]-'A' ] )
69             {
70                 count++;  alpha[ relation[2]-'A' ] = true;
71             }
72             if( determined==0 )
73             {
74                 t = toposort( count );
75                 if( t==-1 )
76                     determined = -1,  k = i + 1;
77                 else if( t==n )
78                     determined = 1,  k = i + 1;
79             }
80         }
81         if( determined==-1 )
82             printf( "Inconsistency found after %d relations.
",k );
83         else if( determined==0 )
84             printf( "Sorted sequence cannot be determined.
" );
85         else
86             printf( "Sorted sequence determined after %d relations: %s.
",k,seq );
87     }
88     return 0;
89 }

/template/Home/DawnNew/PC/Static

立即注册风纳云账号,免费体验多款产品

立即注册