Time Limit: 1000MS Memory Limit: 10000KB 64bit IO Format: %lld & %llu

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.

Source


略蛋疼的拓扑排序,每读入一条边都要跑一次。我刚开始只要发现队列中有多个元素就返回,居然神奇的过样例了,但这么搞是有问题的,不知道是有环还是有很多条路,也不知道是不是点没连完(没连的点入度都是0,会进队)。另外,输出答案后如果数据没读完要读完,否则就被下一组case读进去了。
AC代码:
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, m;
struct node
{
	int v, next;
}e[100000];
int k, head[100000];
int in[30], ans[30], cnt;
queue <int> q;
void adde(int u, int v)
{
	e[k].v = v;
	e[k].next = head[u];
	head[u] = k++;
	in[v]++;
}
int topsort()
{
	while (!q.empty())
		q.pop();
	for (int i = 0; i < n; i++)
		if (!in[i])
			q.push(i);
	cnt = 0;
	int in2[30];
	memcpy(in2, in, sizeof(in));
	bool flag = 0;
	while (!q.empty())
	{
		if (q.size() > 1)
			flag = 1;
		int u = q.front();
		q.pop();
		ans[cnt++] = u;
		for (int i = head[u]; i != -1; i = e[i].next)
		{
			int v = e[i].v;
			if (!(--in2[v]))
				q.push(v);
		}
	}
	if (cnt != n)//环
		return 0;
	if (flag)//不确定 
		return 1;
	return 2;//唯一 
}
int main()
{
	while (scanf("%d %d\n", &n, &m) && n && m)
	{
		char a, b;
		k = 1;
		memset(head, -1, sizeof(head));
		memset(in, 0, sizeof(in));
		bool ok = 0;
		for (int i = 1; i <= m; i++)
		{
			scanf("%c<%c\n", &a, &b);
			if (!ok)
			{
				adde(a - 'A', b - 'A');
				int rc = topsort();
				if (rc == 2)
				{
					printf("Sorted sequence determined after %d relations: ", i);
					for (int j = 0; j < cnt; j++)
						printf("%c", ans[j] + 'A');
					printf(".\n");
					ok = 1;
				}
				else if (rc == 0)
				{
					printf("Inconsistency found after %d relations.\n", i);
					ok = 1;
				}
			}
		}
		if (!ok)
			printf("Sorted sequence cannot be determined.\n");
	}
	return 0;
}

 

分类: ACM/ICPC

发表评论

电子邮件地址不会被公开。 必填项已用*标注