HDU 5348：歐拉路徑與邊刪除技巧實現 O(n+m) 遍歷

問題描述

給定無向圖，需找到一條路徑使得每條邊恰好遍歷一次（歐拉路徑）。關鍵在於從奇度頂點開始搜索，並即時刪除已遍歷邊，保證線性時間複雜度。

核心算法：Hierholzer 算法變體

• 奇度頂點起始：歐拉路徑必定從奇度頂點開始，終止於另一奇度頂點。
• 邊刪除標記：遍歷邊後立即從鏈表中移除，避免重複訪問，實現 O(n+m) 複雜度。
• 雙向邊存儲：每條無向邊拆分為兩條有向邊，利用 f 指針記錄反向邊索引，便於快速刪除。

關鍵代碼實現

void euler(int u) {
    while (head[u] != -1) {
        int v = head[u];
        // 根據邊編號奇偶性標記答案
        if (v & 1) ans[v ^ 1] = 0;
        else ans[v] = 1;
        // 刪除邊：從鏈表移除並更新反向邊
        head[u] = es[v].n;
        es[es[v ^ 1].f].n = es[v ^ 1].n;
        d[es[v].y]--; d[es[v].x]--;
        u = es[v].y;
    }
}

流程說明

1. 讀入圖，構建邊表，統計度數。
2. 優先從奇度點啟動 euler，再處理剩餘非零度點（針對多連通分量）。
3. 輸出邊的方向標記（0/1）。

複雜度與優勢

時間 O(n+m)，空間 O(n+m)。邊刪除技巧避免了 vis 數組的額外開銷，適合大規模稀疏圖。