uva-10129-欧拉通路

题意:每一个单词的长度最小2,最大1000,单词开头的字母和另外一个单词的末尾一样就可以连接起来,解所有的单词是不是都可以连接起来,没有遗漏的

把每一个单词的第一个字母当成一个结点,最后一个单词也作为一个结点,表示第一个字母有一条路径走到最后一个单词,题目的意思就转化为,单词开头字母和结尾

字母组成的图是不是一个联通图,并且这个图存在欧拉通路.

欧拉通路判定(不一定是成环),图中只有俩个结点的度是奇数,终点的入度比出度大1,起点的出度比入度大1,其他点的入度必须等于出度.

欧拉通路的判断+起点和终点的出度等于入度那就是欧拉回路了,但是这个题只要判断通路.

使用了并查集判断图是否联通.

AC时间:30ms

#include <iostream>

#include<stdio.h>

#include<math.h>

#include<memory.h>

using namespace std;

int const max = 'z';

int const min = 'a';

int const length = 'z' - 'a' + 1;

void _init(int *a, int length);

int find(int key, int *a);

void join(int k1, int k2, int *a);

int main()

{

	freopen("d:\\1.txt", "r", stdin);

	int c;

	cin >> c;

	string yes = "Ordering is possible.";

	string no = "The door cannot be opened.";

	while (c--)

	{

		int n;

		cin >> n;

		string str;

		if (n == 1)

		{

			cin >> str;

			cout << yes << endl;

			continue;

		}

		int set[length];

		int duIn[length];

		int duOut[length];

		int vis[length];

		memset(vis, 0, sizeof(vis));

		memset(duIn, 0, sizeof(duIn));

		memset(duOut, 0, sizeof(duIn));

		_init(set, length);

		while (n--)

		{

			cin >> str;

			int s, e;

			s = str[0];

			s -= 'a';

			e = str[str.length() - 1];

			e -= 'a';

			duOut[s]++;

			duIn[e]++;

			vis[s] = 1;

			vis[e] = 1;

			join(s, e, set);

		}

		//判断度和根结点

		int p = -1;

		int s = 0;

		int ok = 1;

		for (int i = 0; i < length; i++)

		{

			if (!vis[i])

				continue;

			int key = find(i, set);

			if (p == -1)

			{

				p = key;

			}

			else if (key != p)

			{

				ok = 0;

				break;

			}

			if (duIn[i] != duOut[i])

			{

				int t = duIn[i] - duOut[i];

				if ((t == -1 || t == 1) && (s <= 1))

				{

					t++;

				}

				else

				{

					ok=0;

					break;

				}

			}

		}

		if (ok)

			cout << yes << endl;

		else

			cout << no << endl;

	}

	return 0;

}

void join(int k1, int k2, int* a)

{

	int p1 = find(k1, a);

	int p2 = find(k2, a);

	if (p1 != p2)

		a[p1] = p2;

}

int find(int key, int *a)

{

	return key == a[key] ? key : a[key] = find(a[key], a);

}

void _init(int* a, int length)

{

	for (int i = 0; i < length; i++)

		a[i] = i;

}