思路与算法

把单词看成一条有向边：首字母是起点，末字母是终点。所有单词排成接龙，等价于每条边恰好经过一次的欧拉道路。统计26个字母的入度、出度，用并查集合并每条边的两端。只检查出现过的字母：它们必须弱连通；入出度要么全部相等，要么恰有一个点出度多1、一个点入度多1，其余相等。按题目规定输出存在性句子。

正确性说明

任意接龙都会经过全部边，因此出现过的字母必然弱连通；除首尾外，每次进入都对应一次离开，得到上述度数条件。反之，若有两个不平衡端点，临时加一条从终点回到起点的边；此时图弱连通且各点入出度相等，存在欧拉回路。去掉临时边便得到原图的欧拉道路；全部平衡时直接有回路。因此条件充要。

复杂度

设所有单词总长为 L，字母表大小为26。读入时间 O(L)，并查集与度数统计近似 O(N)；额外空间为 O(26+最长单词长度)。

易错点

重复单词是不同的边，不能去重。互不连通的自环即使度数平衡也无解。题目要求欧拉道路，首尾不一定相同；本题输出只需要规定的判断句子。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int in[26] = {}, out[26] = {}, p[26];
        iota(p, p + 26, 0);
        function<int(int)> find = [&](int u) {
            return p[u] == u ? u : p[u] = find(p[u]);
        };
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            int a = s.front() - 'a', b = s.back() - 'a';
            out[a]++;
            in[b]++;
            p[find(a)] = find(b);
        }
        int start = 0, end = 0, component = -1;
        bool ok = true;
        for (int i = 0; i < 26; i++) {
            if (in[i] || out[i]) {
                if (component < 0)
                    component = find(i);
                else if (component != find(i))
                    ok = false;
            }
            int d = out[i] - in[i];
            if (d == 1)
                start++;
            else if (d == -1)
                end++;
            else if (d != 0)
                ok = false;
        }
        ok &= (start == 0 && end == 0) || (start == 1 && end == 1);
        cout << (ok ? "Ordering is possible." : "The door cannot be opened.") << '\n';
    }
}