POJ 1041 John's Trip：無向圖歐拉迴路 + 字典序最小路徑

尋找無向圖中從起點出發經過每條邊恰好一次並回到起點的迴路（歐拉迴路）。若多解，輸出邊編號序列字典序最小者。街道編號 1..n (<1995)，路口 1..m (≤44)。

判定條件

• 所有頂點度數為偶數。
• 圖連通（題目保證）。

Hierholzer 算法求字典序最小

對每個頂點的鄰接邊按編號升序排列。DFS 時優先取最小編號邊，遞歸返回後將邊編號加入答案棧。最終反轉棧即為字典序最小路徑。

參考代碼

#include 
using namespace std;
const int MAXN = 2000;
struct Edge { int u, v; } edges[MAXN];
int deg[MAXN], vis[MAXN], ans[MAXN], top;
int n, start;

void dfs(int u) {
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && (edges[i].u == u || edges[i].v == u)) {
            vis[i] = 1;
            dfs(edges[i].u + edges[i].v - u);
            ans[++top] = i;
        }
    }
}

bool check() {
    for (int i = 1; i <= 44; i++) if (deg[i] % 2) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y, z;
    while (cin >> x >> y && x) {
        memset(deg, 0, sizeof deg);
        memset(vis, 0, sizeof vis);
        n = 0; start = min(x, y);
        cin >> z;
        edges[z] = {x, y}; deg[x]++; deg[y]++; n = max(n, z);
        while (cin >> x >> y && x) {
            cin >> z;
            edges[z] = {x, y}; deg[x]++; deg[y]++; n = max(n, z);
        }
        if (check()) {
            top = 0;
            dfs(start);
            for (int i = top; i >= 1; i--) cout << ans[i] << (i==1?'\n':' ');
        } else {
            cout << "Round trip does not exist.\n";
        }
    }
    return 0;
}

關鍵點

• 邊編號即為街道編號，按編號 1..n 迭代天然保證字典序優先。
• 起點為輸入第一條邊的較小端點（題目指定）。
• 多組測試，以空塊 (0 0) 結束。