pku1094.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
int path[26][26];
int in[26];
int N, X;
char res[27];

int Sort()
{
	int stack[26];
	int stack_size, res_size;
	int i, j, flag, p;
	for (i = 0; i < N; i++)
	{
		in[i] = 0;
		for (j = 0; j < N; j++)
		{
			if (path[j][i])
				in[i]++;
		}
	}
	flag = 1;
	stack_size = 0;
	res_size = 0;
	for (i = 0; i < N; i++)
	{
		if (in[i] == 0)
			stack[stack_size++] = i;
	}
	while (stack_size)
	{
		if (stack_size > 1)
			flag = 0;
		p = stack[--stack_size];
		res[res_size++] = p + 'A';
		for (i = 0; i < N; i++)
		{
			if (path[p][i])
			{
				in[i]--;
				if (in[i] == 0)
				{
					stack[stack_size++] = i;
				}
			}
		}
	}
	if (res_size != N)
		return -1;
	return flag;
}

void Solve()
{
	char s[4];
	int i, ans, k;
	memset(path, 0, sizeof(path));
	for (i = 0, k = 0, ans = 0; i < X; i++)
	{
		scanf("%s", s);
		if (ans)
			continue;
		path[s[0] - 'A'][s[2] - 'A'] = 1;
		ans = Sort();
		k = i + 1;
	}
	res[N] = 0;
	if (ans == 0)
		printf("Sorted sequence cannot be determined.\n");
	else if (ans == -1)
		printf("Inconsistency found after %d relations.\n", k);
	else
	{
		printf("Sorted sequence determined after %d relations: %s.\n", k, res);
	}
}

int main()
{
	while (EOF != scanf("%d %d", &N, &X) && N && X)
		Solve();
	return 0;
}