欧拉路径求解

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

const int N=505;
int n=500, m;
int g[N][N];
vector<int> ans;
int deg[N];

void dfs(int u){
    for(int i=1; i<=n; ++i){
        if(g[u][i]){
            g[u][i]--;
            g[i][u]--;
            dfs(i);
        }
    }
    ans.push_back(u);
}

int main(){
    memset(g, 0x00, sizeof g);
    memset(deg, 0x00, sizeof deg);
    cin>>m;
    for(int i=0; i<m; ++i){
        int a, b; // 读入无向图
        cin>>a>>b;
        g[a][b]++;
        g[b][a]++;
        deg[a]++;
        deg[b]++;
    }

    // 从小到大开始找Euler Path
    int k=1;
    while(!deg[k]) ++k;
    for(int i=k; i<=n; ++i){ // 确定起点
        if(deg[i]&0x01) {k=i; break;}
    }
    dfs(k);

    for(int i=ans.size()-1; i>=0; --i) cout<<ans[i]<<endl;
    return 0;
}