play on words(欧拉图，半欧拉图判定).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int n,t;
char word[1100];
bool ex[30];
int in[30], out[30];
int father[30];

void union_find(int s,int e)
{
	int ts = s, te = e;
	while(s != -1 && father[s] != s) {
		s = father[s];
	}
	if(s == -1) {
		father[ts] = s = ts;
	}
	while(e != -1 && father[e] != e) {
		int t = e;
		e = father[e];
		father[t] = s;
	}
	if(e >= 0) {
		father[e] = s;
	}
}

int main()
{
	int i,j;
	int chs,che;
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		getchar();
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		memset(father,-1,sizeof(father));
		for(i=0;i<n;i++) {
			gets(word);
			chs = word[0] -'a';
			che = word[ strlen(word) -1] -'a';
			out[chs] ++;
			in[che] ++;
			union_find(chs,che);
		}
		int set,is,os;
		bool flag = true;
		set = is = os = 0;
		for(i=0;i<26;i++) {
			if(i == father[i]) {
				set ++;
			}
			if(out[i] - in[i] == 1) {
				is ++;
			}
			else if(out[i] - in[i] == -1) {
				os ++;
			}
			else if(out[i] != in[i]) {
				flag = false;
			}
		}
		//有向图 为欧拉图，当且仅当 的基图 连通，且所有顶点的入度等于出度。
		//有向图 为半欧拉图，当且仅当 的基图连通，且存在一个顶点的入度比出度大1，另一个的入度比出度小1，其它所有顶点的入度等于出度。
		if(!flag || set > 1) {
			puts("The door cannot be opened.");
		}
		else {
			if((is == 1 && os == 1) || (is == 0 && os == 0)) {
				puts("Ordering is possible.");
			}
			else {
				puts("The door cannot be opened.");
			}
		}
	}
}