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个不等式，从1到m个不等式，问到第几个不等式的时候能确定字母间的大小关系，或者会出现矛盾（拓扑环），如果到m个不等式都无法确定，那就是无序的。：：
注：这个从1到m是题目中没有给出的，但是题目确实是判断最少不等式确定有序，或者确定矛盾，如果都无法确定才认为是无序的。思路：其实主要就是拓扑排序，拓扑排序过程中，如果没有入度为0的点，那么就存在环，就是矛盾的，floyd可有可无。
如果出现多个零点进入队列，那么就是无序的，但是无序优先级最低，所以不能立即退出，需要继续拓扑排序，判断完所有点入度情况，看看是否存在矛盾。
至于加入的floyd，由于floyd可以直接处理传递关系，就可以直接判出是否存在矛盾，然后，如果这时候再出现无序就能直接退出。（若不使用floyd，代码如注释）
#include<queue>
#include<cstdio>
#include<cstring> using namespace std; int n,m; int maps[][];
struct Node
{
int a,b;
int val;
Node(int a=,int b=,int val=):a(a),b(b),val(val) {}
} node[]; int ans[];
bool topsort()
{
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
maps[i][j] |= maps[i][k] & maps[k][j];
}
}
}
for(int i=;i<=n;i++)if(maps[i][i])return ;
return ;
} int check()
{
if(topsort())return -;
int ind[];
memset(ind,,sizeof(ind));
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(maps[i][j])
{
ind[j]++;
}
}
}
int tot,top,flag=;
for(int i=;i<=n;i++)
{
tot = ;
for(int j=;j<=n;j++)
{
if(!ind[j])
{
tot++;
top = j;
}
}
if(tot >= ) return ;
// if(tot >= 2)flag = 0;
// if(!tot)return -1;
ans[i] = top;
ind[top] = -;
for(int i=;i<=n;i++)
{
if(maps[top][i])ind[i]--;
}
}
// return flag;
return ;
} int main()
{
while(~scanf("%d%d",&n,&m)&&n&&m)
{
int flag = ;
memset(maps,,sizeof(maps));
char a,b,c;
for(int i=; i<=m; i++)
{
scanf(" %c %c %c",&a,&b,&c);
if(b == '<')
maps[a-'A'+][c-'A'+] = ;
else
maps[c-'A'+][a-'A'+] = ;
if(!flag)
{
flag = check();
if(flag == )
{
printf("Sorted sequence determined after %d relations: ",i);
for(int j=; j<=n; j++)
printf("%c",ans[j]+'A'-);
puts(".");
}
else if(flag == -)
{
printf("Inconsistency found after %d relations.\n",i);
}
}
if(i == m && !flag)
printf("Sorted sequence cannot be determined.\n");
}
}
}
