lessons/参考实现/01-欧拉路径/HDU-1116.cpp

#include <array>
#include <iostream>
#include <numeric>
#include <string>
using namespace std;

struct DSU {
    array<int, 26> p{};
    DSU() { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) p[a] = b;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        array<int, 26> in{}, out{};
        array<bool, 26> seen{};
        DSU dsu;
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            int u = s.front() - 'a';
            int v = s.back() - 'a';
            ++out[u]; ++in[v];
            seen[u] = seen[v] = true;
            dsu.unite(u, v);
        }

        int root = -1;
        bool ok = true;
        for (int v = 0; v < 26; ++v) if (seen[v]) {
            if (root == -1) root = dsu.find(v);
            else if (dsu.find(v) != root) ok = false;
        }
        int plus = 0, minus = 0;
        for (int v = 0; v < 26; ++v) {
            int diff = out[v] - in[v];
            if (diff == 1) ++plus;
            else if (diff == -1) ++minus;
            else if (diff != 0) ok = false;
        }
        ok = ok && ((plus == 0 && minus == 0) || (plus == 1 && minus == 1));
        cout << (ok ? "Ordering is possible.\n"
                    : "The door cannot be opened.\n");
    }
}