Sorting It All Out

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions:39731		Accepted: 13975

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 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.

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.

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

Sorted sequence determined after 4 relations: ABCD.

Inconsistency found after 2 relations.

Sorted sequence cannot be determined.

 #include<iostream>

 //#include<bits/stdc++.h>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<set>

 #include<climits>

 using namespace std;

 typedef long long LL;

 #define N 100010

 #define pi 3.1415926535

 #define inf 0x3f3f3f3f

 int n, m;

 int g[][], tmpg[][];

 int floyd()

 {

     for(int i = ; i < n; i++){

         for(int j = ; j < n; j++){

             tmpg[i][j] = g[i][j];

         }

     }

     for(int k = ; k < n; k++){

         for(int i = ; i < n; i++){

             for(int j = ; j < n; j++){

                 tmpg[i][j] |= tmpg[i][k] & tmpg[k][j];

                 if(tmpg[i][j] == tmpg[j][i] && tmpg[i][j] ==  && i != j){

                     return -;

                 }

             }

         }

     }

     for(int i = ; i < n; i++){

         for(int j = ; j < n; j++){

             if(tmpg[i][j] == tmpg[j][i] && tmpg[i][j] ==  && i != j){

                 return ;

             }

         }

     }

     return ;

 }

 struct node{

     int deg;

     char ch;

 };

 bool cmp(node a, node b)

 {

     return a.deg > b.deg;

 }

 void print()

 {

     //int deg[30];

     //memset(deg, 0, sizeof(deg));

     node character[];

     for(int i = ; i < n; i++){

         character[i].deg = ;

         character[i].ch = 'A' + i;

     }

     for(int i = ; i < n; i++){

         for(int j = ; j < n; j++){

             if(tmpg[i][j]){

                 character[i].deg++;

             }

         }

     }

     sort(character, character + n, cmp);

     for(int i = ; i < n; i++){

         printf("%c", character[i].ch);

     }

     printf(".\n");

     /*queue<int>que;

     for(int i = 0; i < n; i++){

         printf("%d\n", deg[i]);

         if(!deg[i]){

             que.push(i);

             break;

         }

     }

     for(int i = 0; i < n; i++){

         int x = que.front();que.pop();

         printf("%c", x + 'A');

         for(int k = 0; k < n; k++){

             if(tmpg[k][x])deg[k]--;

             if(!deg[k])que.push(k);

         }

     }*/

 }

 int main()

 {

     while(scanf("%d%d", &n, &m) != EOF && n || m){

         memset(g, , sizeof(g));

         /*for(int i = 0; i < n; i++){

             g[i][i] = 1;

         }*/

         int i;

         bool dont = false;

         for(i = ; i <= m; i++){

             char a, b;

             getchar();

             scanf("%c<%c", &a, &b);

             g[a - 'A'][b - 'A'] = ;

             if(!dont){

                  int flag = floyd();

                 if(flag == -){

                     printf("Inconsistency found after %d relations.\n", i);

                     dont = true;

                 }

                 else if(flag == ){

                     printf("Sorted sequence determined after %d relations: ", i);

                     print();

                     dont = true;

                 }

             }

         }

         if(i > m && !dont){

             printf("Sorted sequence cannot be determined.\n");

         }

     }

     return ;

 }