单词游戏 欧拉回路

// 单词游戏.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://ybt.ssoier.cn:8088/problem_show.php?pid=1528

https://loj.ac/p/10106
来自 ICPC CERC 1999/2000，有改动。

有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，
前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。

【输入】
多组数据。第一行给出数据组数 T，每组数据第一行给出盘子数量 N，接下去 N 行给出小写字母字符串，一种字符串可能出现多次。

【输出】
若存在一组合法解输出Orderingispossible.，否则输出Thedoorcannotbeopened.。

【输入样例】
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
【输出样例】
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
【提示】
数据范围与提示

1≤N≤105,∣S∣≤1000
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <string>
#include <unordered_map>


using namespace std;



const int N = 1010, M = 400010;
int h[N], e[M], ne[M], idx;
int t, n;
int din[N],dout[N]; int cnt;
int used[M];
int ans[M];
unordered_map<int, string> mm;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
	for (int& i = h[u]; i != -1; ) {

		int j = e[i];
		i = ne[i];
		dfs(j);

		ans[cnt++] = u;
	}
}

int main() {
	cin >> t;
	while (t--) {
		memset(h, -1, sizeof h);
		memset(din, 0, sizeof din);
		memset(dout, 0, sizeof dout);
		memset(used, 0, sizeof used);
		idx = 0; cnt = 0;

		cin >> n;
		int start = 0;
		for (int i = 0; i < n; i++) {
			string str; cin >> str;
			int a = str.front() - 'a'; int b = str.back() - 'a';
			add(a, b); 
			
			dout[a]++; din[b]++; start = a; 
		}
		
		int scnt = 0; int ecnt = 0;
		for (int i = 0; i < 26; i++) {
			if (din[i] != dout[i]) {
				if (dout[i] == din[i] + 1) { scnt++; start = i;}
				else if (din[i] == dout[i] + 1) { ecnt++;  }
				else {
					scnt = 999;
				}
			}
		}

		if ( (scnt != 1 || ecnt != 1) && (scnt!=0||ecnt!=0)) {
			cout << "The door cannot be opened." << endl;
			continue;
		}
		

		dfs(start);

		if (cnt == n) {
			cout << "Ordering is possible." << endl;
		}
		else {
			cout << "The door cannot be opened." << endl;
		}
		
	}


	return 0;
}