Sorting It All Out
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 26866 |
|
Accepted: 9267 |
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
Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
要看清题。。。。
Sorted sequence determined after 4 relations: ABCD.
输入前4个关系后，决定出了一个序列（关系总数可能大于4）
Inconsistency found after 2 relations.
输入前2个关系后，冲突出现了（环，关系总数可能大于2）
Sorted sequence cannot be determined.
所有关系输入后，序列和冲突均无出现
#include
#include
#include
#include
#include
#include
using namespace std; const int M = 30 ; const int N = 1000 + 50; int n, m; char inchar[N][M]; char outchar[M]; int in[M]; int cut; vector
amap[M]; int flag; int toposort() { cut = 0; queue
que; int temp[M]; memcpy( temp, in, sizeof( in ) ); bool all_out = true; //是否是全序的标记 for( int i=0; i
1 ) //若队列里不是一个元素时，就不是全序的了 all_out = false; int a = que.front(); que.pop(); outchar[ cut++ ] = a + 'A'; for( int i=0; i