UVA 10054 The Necklace：歐拉迴路構造與實現

題目大意

妹妹的項鍊斷了，珠子散落一地。每顆珠子有兩個顏色（用 1~50 的整數表示），相鄰珠子在接觸點顏色相同。給出 N 顆收集到的珠子（每顆給出兩端顏色），判斷能否用所有珠子重組成一條閉合項鍊（即首尾顏色也相同）。若可能，輸出任一合法排列；否則輸出 "some beads may be lost"。

核心觀察：無向圖的歐拉迴路

• 將顏色視為頂點，珠子視為無向邊連接其兩端顏色。
• 重組項鍊相當於在圖中找一條經過每條邊恰好一次的閉合路徑，即歐拉迴路。
• 無向圖存在歐拉迴路的充要條件：
  1. 圖是連通的（忽略孤立點）。
  2. 所有頂點的度數均為偶數。

算法流程

1. 讀入測試案例數 T。
2. 對每個案例：
   a. 初始化鄰接矩陣 g[51][51] 記錄邊數，度數陣列 deg[51]，並列集合 p[51] 檢查連通性。
   b. 讀入 N 條邊，更新 g、deg、並查集。
   c. 檢查所有度數 > 0 的頂點是否在同一連通分量，且所有度數為偶數。若否，輸出 "some beads may be lost"。
   d. 否則，從任意度數 > 0 的頂點出發，用Hierholzer 算法（DFS 回溯輸出）構造歐拉迴路。
   e. 輸出路徑（每行一條邊的兩端顏色，順序與走向一致）。

Hierholzer 算法關鍵點

void dfs(int u) {
    for (int v = 1; v <= 50; ++v) {
        while (g[u][v] > 0) {   // 多重邊需用 while
            g[u][v]--; g[v][u]--;
            dfs(v);
            printf("%d %d\n", v, u); // 回溯時輸出，保證順序正確
        }
    }
}

• 遞歸深度 ≤ N ≤ 1000，安全。
• 輸出順序為「退遞歸時輸出」，自然得到正向路徑。
• 題目允許任意合法解，無需字典序最小。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXC = 50;
int g[MAXC+1][MAXC+1], deg[MAXC+1], p[MAXC+1];

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

void dfs(int u) {
    for (int v = 1; v <= MAXC; ++v) {
        while (g[u][v]) {
            g[u][v]--; g[v][u]--;
            dfs(v);
            printf("%d %d\n", v, u);
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n; scanf("%d", &n);
        memset(g, 0, sizeof(g));
        memset(deg, 0, sizeof(deg));
        for (int i = 1; i <= MAXC; ++i) p[i] = i;
        for (int i = 0; i < n; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u][v]++; g[v][u]++;
            deg[u]++; deg[v]++;
            p[find(u)] = find(v);
        }
        bool ok = true;
        int start = -1;
        for (int i = 1; i <= MAXC; ++i) {
            if (deg[i] % 2) ok = false;
            if (deg[i] > 0 && start == -1) start = i;
        }
        // 連通性檢查
        for (int i = 1; i <= MAXC; ++i)
            if (deg[i] > 0 && find(i) != find(start)) ok = false;

        printf("Case #%d\n", cas);
        if (!ok) {
            puts("some beads may be lost");
        } else {
            dfs(start);
        }
        if (cas < T) puts(""); // 案例間空行
    }
    return 0;
}

複雜度

• 時間：O(N + C²) ≈ O(N)，C=50 為常數。
• 空間：O(C²) = O(1)。

總結

經典的無向圖歐拉迴路模板題。關鍵在於正確建模、判斷充要條件、並用 Hierholzer 算法輸出路徑。注意多重邊處理（while 而非 if）與案例間空行格式。