Sorting It All Out
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 26683 | Accepted: 9220 |
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.
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.
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.
Source
East Central North America 2001
传送门:【POJ】1094 Sorting It All Out
传送门:【POJ】1094 Sorting It All Out
题目大意:给n个字母,以及字母间的关系,问能否找到确切的长度为n的字母排列(后面的大于前面的),输出有环或者不能确定或者存在。
题目分析:添加一条边就拓扑排序一次,写起来略烦。。。。不过还是1Y了。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define clear( a , x ) memset ( a , x , sizeof a ) #define copy( a , b ) memcpy ( a , b , sizeof a ) typedef long long Int ; const int MAXN = 27 ; const int MAXE = 1000000 ; const int INF = 0x3f3f3f3f ; struct Edge { int v , n ; } ; Edge edge[MAXE] ; int adj[MAXN] , cntE ; int in[MAXN] , rin[MAXN] ; int d[MAXN] ; int Q[MAXN] , head , tail ; int G[MAXN][MAXN] ; int n , m ; int tot ; int vis[MAXN] ; int ans[MAXN] ; void addedge ( int u , int v ) { edge[cntE].v = v ; edge[cntE].n = adj[u] ; adj[u] = cntE ++ ; } int DAG ( int idx ) { head = tail = 0 ; clear ( d , 0 ) ; copy ( in , rin ) ; int num = 0 ; REP ( i , n ) if ( !in[i] ) Q[tail ++] = i , d[i] = 1 ; while ( head != tail ) { int u = Q[head ++] ; ans[num ++] = u ; for ( int i = adj[u] ; ~i ; i = edge[i].n ) { int v = edge[i].v ; if ( d[v] < d[u] + 1 ) d[v] = d[u] + 1 ; if ( 0 == ( -- in[v] ) ) Q[tail ++] = v ; } } if ( num < tot ) { printf ( "Inconsistency found after %d relations.\n" , idx ) ; return 1 ;//cycle } int cnt = 0 ; REP ( i , n ) if ( d[i] > cnt ) cnt = d[i] ; if ( cnt == n ) { printf ( "Sorted sequence determined after %d relations: " , idx ) ; REP ( i , num ) printf ( "%c" , ans[i] + 'A' ) ; printf ( ".\n" ) ; return 1 ;//ok } else return 0 ;//not found } void work () { int u , v ; char s[5] ; while ( ~scanf ( "%d%d" , &n , &m ) && ( n || m ) ) { clear ( adj , -1 ) ; clear ( rin , 0 ) ; clear ( vis , 0 ) ; cntE = 0 ; tot = 0 ; int ok = 0 ; REPF ( i , 1 , m ) { scanf ( "%s" , s ) ; if ( ok ) continue ; u = s[0] - 'A' ; v = s[2] - 'A' ; if ( !vis[u] ) tot ++ , vis[u] = 1 ; if ( !vis[v] ) tot ++ , vis[v] = 1 ; ++ rin[v] ; addedge ( u , v ) ; ok = DAG ( i ) ; } if ( !ok ) printf ( "Sorted sequence cannot be determined.\n" ) ; } } int main () { work () ; return 0 ; }