HDU 1116 Play on Words：歐拉路/回路判定 + 並查集連通性檢查

問題描述

給定 n 個單詞，判斷能否排成一列，使**前一個單詞的尾字母 = 後一個單詞的首字母** (首尾相接)。多測試用例。
本質：**有向圖中是否存在歐拉路徑 (Eulerian Path) 或歐拉迴路 (Eulerian Circuit)**。

圖模型轉換

• 26 個小寫字母 → 26 個頂點 (0-25)。
• 每個單詞 → 一條**有向邊** 首字母 -> 尾字母。
• 統計每個頂點的 **出度** (out[u]++) 和 **入度** (in[v]++)。

歐拉路/回路存在條件 (有向圖)

1. 連通性：所有**有邊的頂點**屬於同一**弱連通分量** (忽略邊方向視為無向圖連通)。用並查集維護。
2. 度數條件：
   • 歐拉迴路：所有頂點 in[v] == out[v]。
   • 歐拉路徑：恰好一個頂點 out - in = 1 (起點)，恰好一個頂點 in - out = 1 (終點)，其餘頂點 in == out。

完整代碼 (C)

#include 
#include 

#define N 26

int parent[N];
int inDeg[N], outDeg[N];
bool used[N]; // 標記出現過的頂點

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

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

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(inDeg, 0, sizeof(inDeg));
        memset(outDeg, 0, sizeof(outDeg));
        memset(used, 0, sizeof(used));
        for (int i = 0; i < N; ++i) parent[i] = i;

        char word[1005];
        for (int i = 0; i < n; ++i) {
            scanf("%s", word);
            int u = word[0] - 'a';
            int v = word[strlen(word) - 1] - 'a';
            outDeg[u]++; inDeg[v]++;
            used[u] = used[v] = true;
            unite(u, v); // 無向連通性
        }

        // 1. 連通性檢查：所有 used 頂點同根
        int root = -1, components = 0;
        for (int i = 0; i < N; ++i) {
            if (used[i]) {
                int r = find(i);
                if (root == -1) root = r;
                else if (r != root) { components = 2; break; }
            }
        }
        if (components > 1) {
            puts("The door cannot be opened.");
            continue;
        }

        // 2. 度數檢查
        int startCandidates = 0, endCandidates = 0;
        bool ok = true;
        for (int i = 0; i < N; ++i) {
            if (!used[i]) continue;
            int diff = outDeg[i] - inDeg[i];
            if (diff == 1) startCandidates++;
            else if (diff == -1) endCandidates++;
            else if (diff != 0) { ok = false; break; }
        }

        if (ok && ((startCandidates == 0 && endCandidates == 0) || // 迴路
                   (startCandidates == 1 && endCandidates == 1))) { // 路徑
            puts("Ordering is possible.");
        } else {
            puts("The door cannot be opened.");
        }
    }
    return 0;
}

關鍵細節避坑

複雜度

• 時間：O(n * L + 26) (L 平均單詞長度)，極快。
• 空間：O(26) 常數級。

擴展：構造具體路徑 (Hierholzer 算法)

若需輸出具體單詞序列，需在圖上跑 Hierholzer 算法 (DFS 疊邊)，並處理多邊 (同首尾字母多單詞) 用鏈表/向量存儲邊 ID，回溯時輸出。本題僅判斷是否存在。