https://vjudge.net/problem/UVA-10129

来 我们来学习一下欧拉路

欧拉路分为欧拉回路与欧拉道路
如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉道路
如果一个回路是欧拉道路 那么这个回路就是欧拉回路
具有欧拉回路的图称为欧拉图 有欧拉路径但是没有欧拉回路的称为半欧拉图

无向图判欧拉路
所有点度都是偶数，或者恰好有两个点度是奇数，则有欧拉路。
若有奇数点度，则奇数点度点一定是欧拉路的起点和终点（道路），否则可取任意一点作为起点。（回路）

有向图判欧拉路

• 每个点的入度等于出度，则存在欧拉回路（任意一点有度的点都可以作为起点）
• 除两点外，所有入度等于出度。这两点中一点的出度比入度大，另一点的出度比入度小，则存在欧拉路。取出度大者为起点，入度大者为终点。

这个题是求欧拉路径 而且这算是一个有向图 把每个单词的首字母和尾字母看成点 字母看成边 先判断出度不等于入度的点有几个 之后在用dfs爆搜一下是否连通
还可以用并查集写这个题 明天更新这方面的东西吧

#include <set>
#include<iostream>
#include <cstdio>
#include <algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 105;

int vis[maxn],in[maxn], out[maxn];
int G[maxn][maxn];
int n, t;

void dfs(int u) {
	vis[u] = true;
	for (int i = 0; i < maxn; i++) {
		if (G[u][i] && !vis[i])
			dfs(i);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) {
		memset(G, 0, sizeof(G));
		memset(in, 0, sizeof(in));
		memset(out, 0, sizeof(out));
		char str[1005];
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> str;
			G[str[0] - 'a'][str[strlen(str) - 1] - 'a']++;//只存第一个字母和最后一个字母
			in[str[strlen(str) - 1] - 'a']++;
			out[str[0] - 'a']++;
		}
		bool flag = true;
		int num1 = 0;
		int num2 = 0;
		int tm = 0;
		for (int i = 0; i < maxn; i++) {
			if (!flag) break;
			if (in[i] != out[i]) {//如果这个字母的出度不等于入度
				if (in[i] == out[i] + 1) {//入度等于出度加一 说明这个点是终点
					num1++;
				}
				else if (out[i] == in[i] + 1) {//起点
					num2++;
					tm = i;
				}
				else {
					flag = false;
					break;
				}
			}
		}
		if (num1 + num2 > 2) flag = false;//入度和出度不等的点的个数大于2
		//接下来我们要确定这个图是否连通 不连通的话就不行
		if (flag) {
			memset(vis, 0, sizeof(vis));
			dfs(tm);
			bool flag2 = 1;
			for (int i = 0; i < maxn; i++) {
				if (in[i] && !vis[i]) {//有入度但是没有访问
					flag2 = false;
					break;
				}
				if (out[i] && !vis[i]) {
					flag2 = false;
					break;
				}
			}
			if (flag2) {
				cout << "Ordering is possible.\n";
			}
			else {
				cout << "The door cannot be opened.\n";
			}
		}
		else {
			cout << "The door cannot be opened.\n";
		}
	}
	return 0;
}