您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 2230 Watchcow：歐拉迴路變體求經過所有邊恰好兩次的路徑

編輯：關於C++

POJ 2230 Watchcow 完整解析

給定無向圖，求從頂點 1 出發經過所有邊恰好兩次並回到頂點 1 的路徑。資料保證有解。這是經典歐拉迴路的變體：將每條邊重複一次，構造雙重圖後求標準歐拉迴路。

核心洞察

原圖每條邊需走兩次，等價於在圖中每條邊加一條平行邊。雙重圖中所有頂點度數均為偶數，必存在歐拉迴路。使用 Hierholzer 算法（DFS 回溯構造）即可求解。

完整 AC 程式碼

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 10024;
const int MAXM = 50048;

struct Edge { int to, next; } edges[MAXM * 4]; // 雙向邊 × 2（每條邊走兩次）
int head[MAXN], edge_cnt;
int used[MAXM * 4];
vector path;

void add_edge(int u, int v) {
    edges[edge_cnt] = {v, head[u]};
    head[u] = edge_cnt++;
}

void dfs(int u) {
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int eid = i / 2; // 原始邊編號
        int dir = i % 2; // 0: 正向, 1: 反向
        int used_idx = eid * 2 + dir;
        
        if (used[used_idx] >= 2) continue; // 該方向已走兩次
        
        used[used_idx]++;
        int v = edges[i].to;
        dfs(v);
        path.push_back(v);
    }
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        edge_cnt = 0;
        memset(head, -1, sizeof(head));
        memset(used, 0, sizeof(used));
        path.clear();
        
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
            add_edge(u, v); // 第二次
            add_edge(v, u);
        }
        
        dfs(1);
        reverse(path.begin(), path.end());
        
        printf("1\n");
        for (int v : path) printf("%d\n", v);
    }
    return 0;
}