單詞鏈接問題：判斷能否排序成首尾相連環（C語言實作）

編輯：關於C語言

問題描述

給定 N 個單詞（1 <= N <= 10000，每詞長 ≤ 100，僅小寫字母）。判斷是否能重新排序這些單詞，使得每個單詞的首字母等於前一個單詞的尾字母。輸出 "Possible" 或 "Impossible"。

範例：

輸入: 2  ok  ok        → Impossible (o→k, o→k 無法連接)
輸入: 2  ok  ko        → Possible   (o→k, k→o 可成環)

圖論建模：歐拉路徑判定

將 26 個小寫字母視為圖的節點，每個單詞是一條有向邊：從首字母指向尾字母。問題轉化為：該有向圖是否存在歐拉路徑（或歐拉迴路）？

有向圖存在歐拉路徑的充要條件：

圖是弱連通的（忽略方向後連通）。
入度等於出度的節點數為 26、或 24（其餘兩節點一個出度=入度+1 為起點，一個入度=出度+1 為終點）。

原碼採用貪心嘗試連接，未嚴格檢查連通性與度數條件，可能對某些案例誤判。下面給出正確的歐拉路徑判定實作。

正確演算法實作（C 語言）

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 10000
#define MAX_LEN 100

int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        int in[26] = {0}, out[26] = {0};
        int parent[26];
        for (int i = 0; i < 26; i++) parent[i] = i;  // 並查集初始化

        char word[MAX_LEN + 1];
        for (int i = 0; i < N; i++) {
            scanf("%s", word);
            int u = word[0] - 'a';
            int v = word[strlen(word) - 1] - 'a';
            out[u]++; in[v]++;

            // 並查集合併（無向連通性）
            auto find = [&](int x) {
                while (parent[x] != x) x = parent[x] = parent[parent[x]];
                return x;
            };
            int ru = find(u), rv = find(v);
            if (ru != rv) parent[ru] = rv;
        }

        // 條件 1：弱連通（所有有邊節點屬於同一連通分量）
        int comp = -1;
        bool connected = true;
        for (int i = 0; i < 26; i++) {
            if (in[i] || out[i]) {
                int r = find(i);
                if (comp == -1) comp = r;
                else if (comp != r) { connected = false; break; }
            }
        }

        // 條件 2：度數平衡
        int start = 0, end = 0;
        bool degree_ok = true;
        for (int i = 0; i < 26; i++) {
            if (out[i] == in[i] + 1) start++;
            else if (in[i] == out[i] + 1) end++;
            else if (in[i] != out[i]) { degree_ok = false; break; }
        }
        degree_ok = degree_ok && ((start == 0 && end == 0) || (start == 1 && end == 1));

        printf("%s\n", (connected && degree_ok) ? "Possible" : "Impossible");
    }
    return 0;
}

關鍵點解析

步驟	說明
建圖	單詞 → 有向邊 (首字母→尾字母)，統計入/出度。
連通性	並查集維護無向連通分量，僅檢查有邊節點是否同一分量。
度數條件	歐拉迴路：所有節點入=出；歐拉路徑：恰一起點(out=in+1)、一終點(in=out+1)。
複雜度	O(N * L + 26) ≈ O(N)，L 為平均單詞長度，極高效。