poj 1094 Sorting It All Out（nyoj 349）

点击打开链接

Sorting It All Out

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 24544	Accepted: 8503

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.      

题目大意是：给出若干个关系，判断是否能判断出各个数的顺序，如果能，那么输出再第几个关系的时候就能确定顺序，如果不能，有两种输出，要么出现矛盾，要么直到所有关系都判断完了也没法确定顺序

使用拓扑排序每次去掉一个入度为0的点

#include<stdio.h>
bool map[27][27];
char str[27];
int tuopu(int total)
{
	bool flag[27] = {0};
	int count = 0;
	int inagree = 0;
	int i, j;
	int f;
	int n = 0;
	int ex;
	int mark;
	bool ex_flag = 0;
	for(ex = 0; ex < total; ex++)
	{
		inagree = 0;
		
		for(i = 0; i < total; i++)
		{
			f = 0;
			if(flag[i] == 1)
				continue;
			for(j = 0; j < total; j++)
			{
				if(map[j][i] == 1 && flag[j] == 0)
				{
					f = 1;
					break;
				}
			}
			if(f == 0)
			{
				inagree++;
				mark = i;
			}
			if(inagree > 1)
			{
				ex_flag = 1;
				break;
			}
		}
		if(inagree == 0 && count < total)
		{
			return -1;
		}
		flag[mark] = 1;
		count ++;
		str[n ++] = 'A' + mark;
	}
	if(ex_flag == 1)
		return 1;
	str[n] = 0;
	return 0;
}
int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m), n != 0 || m != 0)
	{
		getchar();
		int i;
		char a, b;
		int flag = 1;
		int mark;
		for(i = 1; i <= m; i++)
		{
			scanf("%c<%c", &a, &b);
			getchar();
			if(flag != -1 && flag != 0)
			{
				map[a - 'A'][b - 'A'] = 1;
				int temp = tuopu(n);
				if(temp == 0)
				{
					flag = 0;//成功
					mark = i;
				}
				else if(temp == -1)
				{
					flag = -1;//矛盾
					mark = i;
				}
			}
		}
		if(flag == 0)
			printf("Sorted sequence determined after %d relations: %s.\n", mark, str);
		else if(flag == 1)
			printf("Sorted sequence cannot be determined.\n");
		else
			printf("Inconsistency found after %d relations.\n", mark);
		int j;
		for(i = 0; i < 27; i++)
		{
			for(j = 0; j < 27; j++)
				map[i][j] = 0;
		}
	}
	return 0;
}