單詞接龍問題：判斷能否重排形成首尾銜接環（圖論歐拉路徑應用）

問題建模

給定 N 個單詞（1 ≤ N ≤ 10000，長度 ≤ 100），判斷是否存在排列使每個單詞首字母等於前一單詞尾字母。等價於：建立有向圖，26 個字母為節點，每個單詞為一條從首字母指向尾字母的有向邊。問題轉化為：有向圖是否存在歐拉路徑（Eulerian Path）。

歐拉路徑存在條件（有向圖）

1. 圖在無向意義下是連通的（所有有邊節點屬於同一連通分量）。
2. 入度與出度滿足以下之一：
   • 所有節點 in-degree == out-degree → 存在歐拉迴路（環）。
   • 恰好一個節點 out-degree = in-degree + 1（起點），一個節點 in-degree = out-degree + 1（終點），其餘節點度數相等 → 存在歐拉路徑（非環）。

演算法流程

1. 初始化 26×26 邊計數矩陣、入出度陣列、並查集結構。
2. 遍歷單詞：
   • 首字母 u = word[0] - 'a'，尾字母 v = word[len-1] - 'a'。
   • out[u]++; in[v]++; edge[u][v]++;
   • 並查集合併 u、v。
3. 檢查連通性：所有 in+out > 0 的節點必須屬於同一並查集根。
4. 檢查度數條件：統計 out-in == 1、in-out == 1、in==out 的節點數，驗證上述條件。
5. 輸出 Possible 或 Impossible。

完整 C 實作（O(N + 26²)）

#include 
#include 
#include 

#define MAX_WORDS 10000
#define MAX_LEN   100
#define ALPHA     26

int parent[ALPHA];
int in_deg[ALPHA], out_deg[ALPHA];
int edge[ALPHA][ALPHA];
bool used[ALPHA];

int find_root(int x) {
    return parent[x] == x ? x : (parent[x] = find_root(parent[x]));
}

void union_set(int a, int b) {
    int ra = find_root(a), rb = find_root(b);
    if (ra != rb) parent[rb] = ra;
}

int main(void) {
    int N;
    while (scanf("%d", &N) == 1) {
        // 初始化
        for (int i = 0; i < ALPHA; i++) {
            parent[i] = i;
            in_deg[i] = out_deg[i] = 0;
            used[i] = false;
            for (int j = 0; j < ALPHA; j++) edge[i][j] = 0;
        }

        char word[MAX_LEN + 1];
        for (int i = 0; i < N; i++) {
            scanf("%s", word);
            int len = strlen(word);
            int u = word[0] - 'a';
            int v = word[len - 1] - 'a';
            out_deg[u]++;
            in_deg[v]++;
            edge[u][v]++;
            used[u] = used[v] = true;
            union_set(u, v);
        }

        // 連通性檢查
        int root = -1;
        bool connected = true;
        for (int i = 0; i < ALPHA; i++) {
            if (used[i]) {
                if (root == -1) root = find_root(i);
                else if (find_root(i) != root) { connected = false; break; }
            }
        }

        // 度數檢查
        int start_nodes = 0, end_nodes = 0;
        bool degree_ok = true;
        for (int i = 0; i < ALPHA; i++) {
            int diff = out_deg[i] - in_deg[i];
            if (diff == 1) start_nodes++;
            else if (diff == -1) end_nodes++;
            else if (diff != 0) { degree_ok = false; break; }
        }
        bool euler = connected && degree_ok &&
                     ((start_nodes == 0 && end_nodes == 0) ||
                      (start_nodes == 1 && end_nodes == 1));

        puts(euler ? "Possible" : "Impossible");
    }
    return 0;
}

原始碼分析與改進點

原始碼採用貪婪模擬（O(N²)），對 N=10000 可能超時。改用圖論歐拉路徑判定可降為 O(N + 26²)，極其高效。並查集處理連通性、度數陣列檢查條件，代碼簡潔且符合題目約束。

測試樣例

輸入:
2
ok
ok
2
ok
ko

輸出:
Impossible
Possible

第一組：兩條 o→k 邊，out[o]=2, in[k]=2，但 in[o]=0, out[k]=0，度數差不符合。
第二組：o→k、k→o 形成環，所有度數平衡，連通，Possible。

總結

單詞接龍本質是有向圖歐拉路徑判定。掌握「連通性 + 入出度條件」兩大核心判據，配合並查集與度數統計，即可在線性時間內解決大規模實例。此類建模技巧廣泛應用於 DNA 片段組裝、郵遞員路徑規劃等領域。