欧拉路径全 WA

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

_XSOI_ @ 2024-05-25 18:57:54

听了一天的课,脑子很昏,欧拉路径打半天没看出错哪了?

求调。

#include <iostream>
using namespace std;
const int MAXX = 10024;
int e[MAXX][MAXX];
int d[MAXX];
int l[MAXX];
int m;
int max_e;
int st, ed;
void dfs(int x) {
    int i;
    for (i = 1; i <= max_e; i ++) {
        if (e[x][i] > 0) {
            e[x][i] --;
            e[i][x] --;
            dfs(i);
        }
    }
    ed ++;
    l[ed] = i;
}
int main() {
    cin >> m;
    for (int i = 1; i <= m; i ++) {
        int x, y;
        cin >> x >> y;
        e[x][y] ++;
        e[y][x] ++;
        d[x] ++;
        d[y] ++;
        max_e = max(max_e, max(x, y));
    }
    for (int i = 1; i <= max_e; i ++) {
        if (d[i] & 1) {
            st = i;
            break;
        }
    }
    dfs(st);
    for (int i = ed; i >= 1; i --) {
        cout << l[i] << "\n";
    }
    return 0;
}

|