[USACO3.3] Riding the Fences - 欧拉回路

求顶点序最小的欧拉路。

Solution

如果图中没有度数为 \(1\) 的点，那么就从 \(1\) 点出发，否则从编号最小的度数为 \(1\) 的点出发

每次贪心地走到一个编号尽可能小的点，然后过河拆桥，删掉这条边

（莫名其妙的最后两个点）

#include <bits/stdc++.h>
using namespace std;

int n=1000,m,a[1005][1005],d[1005],t1,t2;
stack <int> s;

void dfs(int p) {
    for(int i=1;i<=n;i++) if(a[p][i]) {
        a[p][i]--;
        a[i][p]--;
        d[i]--;
        d[p]--;
        dfs(i);
    }
    s.push(p); //?
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>m;
    for(int i=1;i<=m;i++) {
        cin>>t1>>t2;
        a[t1][t2]++;
        a[t2][t1]++;
        d[t1]++;
        d[t2]++;
    }
    int v0;
    for(int i=n;i;--i) if(d[i]) v0=i;
    for(int i=n;i;--i) if(d[i]&1) v0=i;
    dfs(v0);
    while(s.size()) cout<<s.top()<<endl, s.pop();
}

[USACO3.3] Riding the Fences - 欧拉回路

原文：https://www.cnblogs.com/mollnn/p/12504720.html