pku1386.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define SIZE 26

int f[SIZE];
int u[SIZE];
int in[SIZE];
int out[SIZE];
char s[1100];
int N;

int root(int x)
{
	return f[x] == -1 ? x : f[x] = root(f[x]);
}

void Insert(int a, int b)
{
	int ha, hb;
	u[a] = 1;
	u[b] = 1;
	in[a]++;
	out[b]++;
	ha = root(a);
	hb = root(b);
	if (ha == hb)
		return;
	if (ha < hb)
		f[hb] = ha;
	else
		f[ha] = hb;
}

int Solve()
{
	int i;
	int a, b, F;
	int incnt, outcnt;
	scanf("%d", &N);
	memset(f, -1, sizeof(f));
	memset(u, 0, sizeof(u));
	memset(in, 0, sizeof(in));
	memset(out, 0, sizeof(out));
	for (i = 0; i < N; i++)
	{
		scanf("%s", s);
		a = s[0] - 'a';
		b = s[strlen(s) - 1] - 'a';
		Insert(a, b);
	}
	F = -1;
	for (i = 0; i < SIZE; i++)
	{
		if (u[i])
		{
			if (F == -1 || F == root(i))
				F = root(i);
			else
				return 0;
		}
	}
	incnt = 0;
	outcnt = 0;
	for (i = 0; i < SIZE; i++)
	{
		if (in[i] - out[i] == 1)
			incnt++;
		else if (in[i] - out[i] == -1)
			outcnt++;
		else if (in[i] == out[i])
			;
		else
			return 0;
	}
	return incnt < 2 && outcnt < 2;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		if (Solve())
			printf("Ordering is possible.\n");
		else
			printf("The door cannot be opened.\n");
}