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. 題目大意：給你兩個數n和m ， n 表示26個大寫英文子母中的前 n 個字母， m 表示以下m個形如：A < B 的表達式。按照這 m 個表達式給出的順序，每給出一個表達式（假設序號為k ，1 <= k <= m），就以這前k個表達式為條件，判斷以下三種情況： 1、前n個大寫英文字母 能 按拓撲序排好 ，並且 只有一種 排列方式。注意：此時k 可能小於 n ！！這時輸出：Sorted sequence determined after xxx relations: yyy...y. 2、前n個大寫英文字母 能 按拓撲序排好 ，但有 不止一種 排列方式。注意：此時k 必須等於 n ！！這時輸出：Sorted sequence cannot be determined. 3、如果不能完成拓撲序，注意：此時k 可能小於 n ！！就輸出：Sorted sequence cannot be determined. 解題思路：每給出一個表達式，就以這個表達式以及這個表達式以前的表達式為條件，進行拓撲排序。 請看代碼：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 100 ;
int ind[MAXN] ;
int idtmp[MAXN] ;
char ans[MAXN] ;
vector<int> G[MAXN] ;
int n , m ;
void chu()
{
mem(ind , 0) ;
mem(idtmp , 0) ;
mem(ans , 0) ;
int i ;
for(i = 0 ; i <= n ; i ++)
G[i].clear() ;
}
int topo()
{
int i ;
mem(idtmp , 0) ;
for(i = 0 ; i < n ; i ++)
{
idtmp[i] = ind[i] ;
}
int k = 0 ;
int sumd0 ;
int u , v ;
bool flag1 , flag2 , flag3 ;
flag2 = false ;
flag3 = true ;
for(k = 0 ; k < n ; k ++)
{
sumd0 = 0 ;
for(i = 0 ; i < n ; i ++)
{
if(idtmp[i] == 0)
{
sumd0 ++ ;
u = i ;
}
}
if(sumd0 > 0)
{
ans[k] = u + 'A';
idtmp[u] -- ;
for(int j = 0 ; j < G[u].size() ; j ++)
{
v = G[u][j] ;
idtmp[v] -- ;
}
if(sumd0 > 1)
{
flag2 = true ;
}
}
else
{
flag3 = false ;
break ;
}
}
if(!flag3)
{
return 3 ;
}
else
{
if(flag2)
{
return 2 ;
}
else
{
return 1 ;
}
}
}
void init()
{
chu() ;
int i ;
char a , op , b ;
bool f = false ;
for(i = 0 ; i < m ; i ++)
{
cin >> a >> op >> b ;
if(f)
continue ;
int ta , tb ;
ta = a - 'A' ;
tb = b - 'A' ;
G[ta].push_back(tb) ;
ind[tb] ++ ;
int pan ;
pan = topo() ;
if(pan == 3)
{
f = true ;
printf("Inconsistency found after %d relations.\n" , i + 1) ;
}
else if(pan == 1)
{
ans[n] = '\0' ;
f = true ;
printf("Sorted sequence determined after %d relations: %s.\n" , i + 1 , ans) ;
}
else if(pan == 2 && i == m - 1)
{
puts("Sorted sequence cannot be determined.") ;
}
}
}
int main()
{
while (scanf("%d%d" , &n , &m) != EOF)
{
if(n == 0 && m == 0)
break ;
init() ;
}
return 0 ;
}
