UVA 10129 Play on Words：並查集 + 歐拉路徑判定

給定一組單詞，每個單詞視為一條從首字母到尾字母的有向邊。判斷能否將所有單詞排成一條首尾相接的鏈（即圖中是否存在歐拉路徑/迴路）。

判定條件（有向圖）

1. 連通性：所有有邊的頂點屬於同一連通分量（用並查集維護）。
2. 度數條件：
   • 歐拉迴路：所有頂點入度 = 出度。
   • 歐拉路徑：恰有一頂點出度 = 入度 + 1 (起點)，一頂點入度 = 出度 + 1 (終點)，其餘相等。

算法流程

1. 初始化 26 個字母的並查集、入度/出度陣列。
2. 讀入每個單詞，統計首尾字母度數，合併並查集。
3. 檢查度數條件，統計連通分量數（父節點為自己的集合數）。
4. 滿足條件輸出 "Ordering is possible."，否則 "The door cannot be opened."。

參考代碼

#include 
using namespace std;

int father[26];
int inDeg[26], outDeg[26];
bool exist[26];

int findFather(int x) {
    return father[x] == x ? x : father[x] = findFather(father[x]);
}

void unite(int a, int b) {
    int fa = findFather(a), fb = findFather(b);
    if (fa != fb) father[fa] = fb;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        fill(father, father+26, 0);
        iota(father, father+26, 0);
        fill(inDeg, inDeg+26, 0);
        fill(outDeg, outDeg+26, 0);
        fill(exist, exist+26, false);

        string w;
        for (int i = 0; i < n; i++) {
            cin >> w;
            int u = w.front() - 'a';
            int v = w.back() - 'a';
            outDeg[u]++; inDeg[v]++;
            exist[u] = exist[v] = true;
            unite(u, v);
        }

        int comp = 0, start = 0, end = 0;
        bool ok = true;
        for (int i = 0; i < 26; i++) if (exist[i]) {
            if (father[i] == i) comp++;
            if (inDeg[i] == outDeg[i]) continue;
            else if (outDeg[i] - inDeg[i] == 1) start++;
            else if (inDeg[i] - outDeg[i] == 1) end++;
            else { ok = false; break; }
        }

        if (ok && comp == 1 && ((start==0 && end==0) || (start==1 && end==1)))
            cout << "Ordering is possible.\n";
        else
            cout << "The door cannot be opened.\n";
    }
    return 0;
}