2318.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2318 on 2006-08-13 at 21:48:10 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int N = 360;
const int L = 32;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

map<char*, int, cmp> dict;
char word[N][L];
int n, nxt[N];
bool head[N];

int order(char*);

int main()
{
	int T;
	
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		int m; scanf("%d", &m); n = 0;
		dict.clear(); memset(head, true, sizeof(head)); memset(nxt, -1, sizeof(nxt));
		for(int i = 1; i < m; i++) {
			char w1[L], w2[L]; scanf("%s %s", w1, w2);
			int o1 = order(w1), o2 = order(w2);
			nxt[o1] = o2; head[o2] = false;
		}
		int index;
		for(int i = 0; i < n; i++)
			if(head[i]) { index = i; break; }
		printf("Scenario #%d:\n", t);
		do {
			printf("%s\n", word[index]);
			index = nxt[index];
		} while(index != -1);
		putchar('\n');
	}
	
	return 0;
}

int order(char* w)
{
	if(!dict.count(w)) {
		strcpy(word[n], w);
		dict[word[n]] = n; n++;
	}
	return dict.find(w)->second;
}