Sorting It All Out
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 28762 | Accepted: 9964 |
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.
Source
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n , m ;
bool map[][] ;
int in[] ;
char st[][] ;
char a[] ; int topo ()
{
queue <int> q ;
int indegree[] ;
int cnt = ;
int k = ;
int ans = - ;//record the condition that "cnt > 1"
while (!q.empty ())
q.pop () ;
for (int i = ; i <= n ; i++)
indegree[i] = in[i] ;
for (int i = ; i <= n ; i++) {
if (in[i] == ) {
q.push (i) ;
cnt++ ;
}
// printf ("%d " , in[i]) ;
}
if (cnt > )
ans = ;//conditons are not satisfied
while (!q.empty ()) {
int temp = q.front () ;
a[k++] = 'A' + temp - ;
q.pop () ;
cnt = ;
for (int i = ; i <= n ; i++) {
if (map[temp][i]) {
indegree[i]-- ;
if (indegree[i] == ) {
cnt++ ;
q.push (i);
}
}
}
if (cnt > )
ans = ;//conditons are not satisfied
}
if (k != n )
return ;//there is a circle
if (k == n && ans != )
return ;//success if (ans == )
return ;
} int main ()
{
// freopen ("a.txt" , "r" , stdin) ;
int link ;
int flag ;
int success ;
while (~ scanf ("%d%d" , &n , &m)) {
if (n == && m ==)
break ;
getchar () ;
memset (in , , sizeof(in)) ;
memset (map , , sizeof(map)) ;
link = - ;
flag = - ;
success = - ;
for (int i = ; i < m ; i++)
gets (st[i]) ; for (int i = ; i < m ; i++) {
int u = st[i][] - 'A' + ;
int v = st[i][] - 'A' + ;
// printf ("u = %d , v = %d\n" , u , v) ;
if (!map[u][v])
in[v]++ ;
map[u][v] = ; flag = topo () ;
if (flag == ) {
link = i + ;
break ;
}
else if(flag == ) {
success = i + ;
break ;
}
// puts ("") ;
}
if (flag == ) {
printf ("Inconsistency found after %d relations.\n" , link) ;
}
else if (flag == ) {
puts ("Sorted sequence cannot be determined.") ;
}
else {
printf ("Sorted sequence determined after %d relations: " , success) ;
for (int i = ; i < n ; i++) {
printf ("%c" , a[i]) ;
}
printf (".\n") ;
}
}
return ;
}
要一条条边测下来，not determined 肯定是最后一条边出来才能 判断 ，但在这之前若 先判断出了 success 或 inconsistency 就能结束了（一开始要把所有边先记录下来）
success只有 无环 & 同一时刻加入队列的点 == 1 时才能 成立