1170.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1170 on 2005-10-29 at 10:29:16 */ 
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;

const int MAX = 32;

char word[MAX];
int ideg[MAX];
int stack[MAX], top;
int list[MAX][MAX], link[MAX];
bool printed[MAX];

void topologySort(int);

int main()
{
	char line[512];
	int i, a, b, t = 0;
	
	while(gets(line) != NULL) {
		top = 0;
		for(i = 0; line[i] != 0; i++) {
			if(line[i] != ' ') {
				stack[top++] = line[i] - 'a';
			}
		}
		gets(line);
		memset(ideg, 0, sizeof(ideg));
		memset(link, 0, sizeof(link));
		for(i = 0; line[i] != 0; ) {
			while(line[i] == ' ') {
				i++;
			}
			a = line[i++] - 'a';
			while(line[i] == ' ') {
				i++;
			}
			b = line[i++] - 'a';
			ideg[b]++;
			list[a][link[a]++] = b;
		}
		memset(printed, false, sizeof(printed));
		memset(word, 0, sizeof(word));
		if(t != 0) {
			putchar('\n');
		}
		t++;
		topologySort(0);
	}
}

void topologySort(int n)
{
	if(n == top) {
		printf("%s\n", word);
		return;
	} else {
		int zstack[MAX], ztop = 0;
		int i, j;
		for(i = 0; i < top; i++) {
			if(ideg[stack[i]] == 0 && !printed[stack[i]]) {
				zstack[ztop++] = stack[i];
			}
		}
		sort(zstack, zstack+ztop);
		for(i = 0; i < ztop; i++) {
			word[n] = zstack[i] + 'a';
			printed[zstack[i]] = true;
			for(j = 0; j < link[zstack[i]]; j++) {
				ideg[list[zstack[i]][j]]--;
			}
			topologySort(n+1);
			for(j = 0; j < link[zstack[i]]; j++) {
				ideg[list[zstack[i]][j]]++;
			}
			printed[zstack[i]] = false;
		}
	}
}