POJ 1041 John's Trip：字典序最小歐拉迴路

題目大意

無向圖，邊有編號。求從 1 號點出發的歐拉迴路（走遍每條邊恰好一次回到起點），要求邊編號序列字典序最小。輸入多組，0 0 結束。

解法：Hierholzer 算法 + 優先遍歷

1. 檢查歐拉迴路條件：連通且所有頂點度數為偶數。
2. 對每個頂點的鄰接邊按編號升序排序。
3. DFS 後序輸出邊編號（或用棧模擬），自然得到字典序最小序列。

關鍵：遞歸進入最小編號邊，回溯時記錄，最終逆序即為正序路徑。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000;

vector> adj[MAXN+1]; // (edge_id, to)
bool used[2000000];
int stk[2000000], top;
int deg[MAXN+1];

void dfs(int u) {
    for (auto &e : adj[u]) {
        if (!used[e.first]) {
            used[e.first] = true;
            dfs(e.second);
            stk[top++] = e.first;
        }
    }
}

int main() {
    int u, v;
    while (cin >> u >> v, u || v) {
        int id; cin >> id;
        for (int i=1;i<=MAXN;i++) { adj[i].clear(); deg[i]=0; }
        memset(used, 0, sizeof(used));
        top = 0;
        int maxV = max(u,v);
        adj[u].push_back({id, v});
        adj[v].push_back({id, u});
        deg[u]++; deg[v]++;
        while (cin >> u >> v, u || v) {
            cin >> id;
            adj[u].push_back({id, v});
            adj[v].push_back({id, u});
            deg[u]++; deg[v]++;
            maxV = max(maxV, max(u,v));
        }
        bool ok = true;
        for (int i=1;i<=maxV;i++) if (deg[i]&1) ok=false;
        for (int i=1;i<=maxV;i++) sort(adj[i].begin(), adj[i].end());
        if (!ok) { cout << "Round trip does not exist.\n\n"; continue; }
        dfs(1);
        if (top == 0) { cout << "Round trip does not exist.\n\n"; continue; }
        for (int i=top-1;i>=0;i--) {
            cout << stk[i];
            if (i) cout << ' ';
        }
        cout << "\n\n";
    }
    return 0;
}

注意點

• 圖可能不連通，DFS 後檢查 top 是否等於邊數。
• 輸出格式：每組後有空行。
• 邊編號可能重複（多重圖），用 used[edge_id] 標記。