1336.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1336 on 2005-11-09 at 22:30:52 */ 
#include <cstdio>
#include <cstring>

const int MAX = 32;
const int INFINITE = 600000;

int topologySort();

bool edge[MAX][MAX];
int t[MAX], n;
char order[MAX];

int main()
{
	int status, min;
	int id[MAX];
	int m, i, j;
	char line[MAX], A, B;

	while(scanf("%d %d", &n, &m) == 2) {
		if(m == 0 && n == 0) {
			return 0;
		} else {
			memset(edge, false, sizeof(edge));
			memset(id, 0, sizeof(id));
			memset(order, 0, sizeof(order));
			status = 0;
			getchar();
			for(i = 1; i <= m; i++) {
				gets(line);
				sscanf(line, "%c%*c%c", &A, &B);
				if(!edge[A-'A'][B-'A'] && status == 0) {
					id[B-'A']++;
					edge[A-'A'][B-'A'] = true;
					for(j = 0; j < n; j++) {
						t[j] = id[j];
					}
					status = topologySort();
					if(status == -1) {
						min = i;
					} else if(status == 1) {
						min = i;
					}
				}
			}
			if(status == 0) {
				printf("Sorted sequence cannot be determined.\n");
			} else if(status == 1) {
				printf("Sorted sequence determined after %d relations: %s.\n", min, order);
			} else {
				printf("Inconsistency found after %d relations.\n", min);
			}
		}
	}

	return 0;
}

int topologySort()
{
	bool inStack[MAX] = {false}, uncertain = false;
	int stack[MAX], top = 0;
	int i, p, k = 0;
	
	for(i = 0; i < n; i++) {
		if(t[i] == 0) {
			stack[top++] = i;
			inStack[i] = true;
		}
	}
	while(top > 0) {
		if(top > 1) {
			uncertain = true;
		}
		p = stack[--top];
		order[k++] = p + 'A';
		for(i = 0; i < n; i++) {
			if(edge[p][i]) {
				t[i]--;
			}
		}
		for(i = 0; i < n; i++) {
			if(t[i] == 0 && !inStack[i]) {
				stack[top++] = i;
				inStack[i] = true;
			}
		}
	}
	for(i = 0; i < n; i++) {
		if(!inStack[i]) {
			return -1;
		}
	}
	if(uncertain) {
		return 0;
	} else {
		return 1;
	}
}