题目大意：给出一些字符串问能不能首尾相连。
解题思路：刚开始想每个词的首尾作为一个节点看看能不能把节点串起来，发现十分复杂。还是靠题解……把每个字母当成点，即每个词是线，然后判断有向欧拉通路。
欧拉道路：除了起点和终点外， 其他点的“进出” 次数应该相等。 对于有向图， 则必须其中一个点的出度恰好比入度大 1， 另一个的入度比出度大 1。
只有第一个字母和最后一个字母有用。然后记录每个字母的入度和出度以及连接这两点的边数。dfs、fun 判断图的连通性，ok 判断度数是否合法。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int map[30][30]; int in[30], out[30]; bool vis[30]; int N; void dfs(int now) { vis[now] = true; for (int i = 0; i < 26; i++) if (map[now][i] > 0) { map[now][i]--; map[i][now]--; dfs(i); } } bool fun() { for (int i = 0; i < 26; i++) if (in[i] + out[i]) if (vis[i] == false) return false; return true; } bool ok() { bool start = false; bool end = false; for (int i = 0; i < 26; i++) if (in[i] != out[i]) if (!end && in[i] == out[i] + 1) end = true; else if (!start && in[i] + 1 == out[i]) start = true; else return false; return true; } int main() { int T; cin >> T; while (T--) { memset(map, 0, sizeof(map)); memset(in, 0, sizeof(map)); memset(out, 0, sizeof(out)); memset(vis, 0, sizeof(vis)); cin >> N; string s; int a, b; for (int i = 0; i < N; i++) { cin >> s; a = s[0] - 'a'; b = s[s.length()-1] - 'a'; out[a]++; in[b]++; map[a][b]++; map[b][a]++; } dfs(a); if (ok() && fun()) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }