欧拉路

给定一个无向图, 求一条恰好经过每条边恰好一次的路径.

如果所有点度数均为偶数, 存在欧拉回路; 如果有且仅有两个点度数为奇数, 存在以这两个点为起点, 终点的欧拉路.

欧拉路是一个连通图, 可以分解为一条点不相交的路径 + 若干个环.

求欧拉路

直接搜索, 那么出栈序列的逆序即为欧拉路.

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;

//---------------------------------------
const int nsz=550,msz=1050;
int n,m;
int deg[nsz];
multiset<int> edge[nsz];
void adde(int f,int t){edge[f].insert(t);edge[t].insert(f);}
void erase(int f,int t){edge[f].erase(edge[f].find(t));}

int ans[nsz],pa=0;
void dfs(int p){
    for(multiset<int>::iterator i=edge[p].begin();i!=edge[p].end();i=edge[p].begin()){
        int v=*i;
        edge[p].erase(i);
        edge[v].erase(edge[v].find(p));
        dfs(v);
    }
    ans[++pa]=p;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>m;
    int a,b;
    rep(i,1,m)cin>>a>>b,++deg[a],++deg[b],adde(a,b),n=max(n,max(a,b));
    int fr=-1;
    rep(i,1,n){
        if(deg[i]&&fr==-1)fr=i;
        if(deg[i]&1){fr=i;break;}
    }
    dfs(fr);
    repdo(i,pa,1)cout<<ans[i]<<'\n';
    return 0;
}