1033.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1033 on 2005-10-30 at 15:50:05 */ 
#include <cstdio>
#include <cstring>

const int N_MAX = 32;
const int L_MAX = 1024;

class UFSet {
public:
	int parent[N_MAX];
	void makeSet() {
		memset(parent, -1, sizeof(parent));
	}
	int find(int x) {
		if(parent[x] == -1) {
			return x;
		} else {
			parent[x] = find(parent[x]);
			return parent[x];
		}
	}
	void unionSet(int x, int y) {
		int pX = find(x);
		int pY = find(y);
		if(pX != pY) {
			parent[pX] = pY;
		}
	}
};

int main()
{
	UFSet uf;
	int ideg[N_MAX], odeg[N_MAX];
	int T, t, n, l, i, p, f;
	char line[L_MAX];
	bool can, begin, end;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d\n", &n);
		memset(ideg, 0, sizeof(ideg));
		memset(odeg, 0, sizeof(odeg));
		uf.makeSet();
		for(i = 0; i < n; i++) {
			gets(line);
			l = strlen(line);
			odeg[line[0]-'a']++;
			ideg[line[l-1]-'a']++;
			uf.unionSet(line[0]-'a', line[l-1]-'a');
		}
		f = -1;
		can = true;
		for(i = 0; i < N_MAX; i++) {
			if(odeg[i] != 0 || ideg[i] != 0) {
				p = uf.find(i);
				if(f == -1) {
					f = p;
				} else if(f != p) {
					can = false;
					break;
				}
			}
		}
		if(can) {
			begin = end = false;
			for(i = 0; i < N_MAX; i++) {
				p = ideg[i] - odeg[i];
				if(p == -1) {
					if(begin) {
						can = false;
						break;
					} else {
						begin = true;
					}
				} else if(p == 1) {
					if(end) {
						can = false;
						break;
					} else {
						end = true;
					}
				} else if(p != 0) {
					can = false;
					break;
				}
			}
		}
		if(can) {
			printf("Ordering is possible.\n");
		} else {
			printf("The door cannot be opened.\n");
		}
	}
	
	return 0;
}