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 6A
    
     
      
       
        
       
      
     
    

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

题意大概是给n个变量m个不等式，不等式之间有传递性，判断这些不等式是否矛盾，若不矛盾，判断能否求出每一对变量的关系，若能求出，判断最少利用前几个不等式。

做法：传递闭包+拓补排序。

利用floyd实现传递闭包，dp[i][j]=1表示i

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int MAXN = 30;int n,m,dp[MAXN][MAXN],d[MAXN];bool flag;char c[4];inline int floyd() {    memset(d,0,sizeof(d));    for(register int k=1; k<=n; k++)        for(register int x=1; x<=n; x++)            for(register int j=1; j<=n; j++) {                if(dp[x][k] && dp[k][j])                    dp[x][j]=1;            }    for(register int i=1; i<=n; i++)        for(register int j=i+1; j<=n; j++) {            if(dp[i][i]==1) return 1;            if(dp[i][j]==1) d[j]++;            if(dp[j][i]==1) d[i]++;            if(dp[i][j]==1 && dp[j][i]==1)                return 1;        }    for(register int i=1; i<=n; i++)        for(register int j=i+1; j<=n; j++)            if(dp[i][j]==0 && dp[j][i]==0)                return 2;    return 3;}int main() {    while(~scanf("%d%d",&n,&m)) {        if(n==0 && m==0) break;        flag=false;        memset(dp,0,sizeof(dp));        for(register int i=1; i<=m; i++) {            scanf("%s",c+1);            if(flag) continue;            dp[c[1]-'A'+1][c[3]-'A'+1]=1;            int u=floyd();            if(u==1) {                printf("Inconsistency found after %d relations.",i);                flag=true;                printf("\n");            } else if(u==3) {                printf("Sorted sequence determined after %d relations: ",i);                queue
        
          q;                for(register int i=1; i<=n; i++)                    if(d[i]==0) {                        q.push(i);                        break;                    }                while(q.size()) {                    int x=q.front();                    q.pop();                    printf("%c",x+'A'-1);                    for(register int i=1; i<=n; i++)                        if(dp[x][i]) {                            d[i]--;                            if(d[i]==0)                                q.push(i);                        }                }                printf(".\n");                flag=true;            }        }        if(!flag)            printf("Sorted sequence cannot be determined.\n");//      for(register int i=1; i<=n; i++) {
    //          for(register int j=1; j<=n; j++) {
    //              cout<
         
          <<" ";// }// cout<