分析

• 这一题的建图方式和AcWing 1165. 单词环是一模一样的，每个单词看成一条边，首字母和为字母看成图中的顶点。这是一个有向图。

• 建完图之后，问题就变成了我们能否找到一条路径，依次走过每条边，即该有向图中是否存在欧拉路径？

• 我们要清楚如何判有向图是否存在欧拉路径，需要满足两个条件：

（1）所有的边要连通；

（2）除了起点和终点外，其余点的入度必须等于出度；

• 对于（1），可以使用并查集解决，如果某个点有边相连，但是和并查集不连通，说明边不连通。

• 本题不需要将所有边存储下来，只需要判断连通性以及记录每个点的入度和出度判断是否存在答案即可。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30;  // 点数最多26个

int n;  // 单词数目，图中对应边数
int p[N];  // 并查集
int din[N], dout[N];
bool st[N];  // 记录某个字母是否作为单词首尾出现过

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {

    char str[1010];

    int T;
    scanf("%d", &T);
    while (T--) {

        cin >> n;

        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(st, 0, sizeof st);
        for (int i = 0; i < 26; i++) p[i] = i;

        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            int a = str[0] - 'a', b = str[strlen(str) - 1] - 'a';
            st[a] = st[b] = true;
            dout[a]++, din[b]++;
            p[find(a)] = find(b);
        }

        // 判断度数是否正确
        int start = 0, end = 0;
        bool success = true;  // 是否存在欧拉路径
        for (int i = 0; i < 26; i++) 
            if (din[i] != dout[i]) {
                if (din[i] == dout[i] + 1) end++;  // 终点数目，只能有1个
                else if (dout[i] == din[i] + 1) start++;  // 起点数目，只能有一个
                else {
                    success = false;
                    break;
                }
            }
        // 判断起点终点数目是否正确
        if (success && !(!start && !end || start == 1 && end == 1)) success = false;

        // 判断所有边是否连通
        int rep = -1;  // 代表元素
        for (int i = 0; i < 26; i++)
            if (st[i]) {  // 说明该字母在单词中出现过，所有st为true的都应该在一个集合中
                if (rep == -1) rep = find(i);
                else if (rep != find(i)) {  // 说明存在边不连通
                    success = false;
                    break;
                }
            }

        if (success) puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }

    return 0;
}