欧拉回路判定

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

const int N=100005;
const int M=400005;

int type, n, m;
int head[N], E=1; // 边的编号从1开始
struct Edge{
    int v, ne;
}e[M];

int din[N], dout[N]; // 记录点的度数
bool vis[M]; // 记录边的访问情况
vector<int> ans;

inline void add(int a, int b){
    ++E;
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E;
}

void dfs(int x){ // find Euler loop
    for(int &i=head[x], v; v=e[i].v, i; i=e[i].ne){
        int c=(type==1?i/2:i-1);
        int sgn=i&0x01;
        if(!vis[c]){
            vis[c]=true;
            dfs(v);
            if(type==1) ans.push_back(sgn? -c: c);
            else ans.push_back(c);
        }
    }
}

int main(){
    memset(head, 0x00, sizeof head);
    memset(vis, 0x00, sizeof vis);
    memset(din, 0x00, sizeof din);
    memset(dout, 0x00, sizeof dout);

    cin>>type>>n>>m;
    for(int i=1; i<=m; ++i){
        int x, y;
        cin>>x>>y;
        add(x, y); // x->y的边
        if(type==1) add(y, x); // 如果是无向边需要添加反向边
        din[y]++; dout[x]++;
    }

    if(type==1){ // 无向图判断: 如果存在点的度数为奇数则不存在Euler loop
        for(int i=1; i<=n; ++i){
            if((din[i]+dout[i])%2){
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }
    else{ // 有向图判断: 如果存在点的出度!=入度则不存在Euler loop
        for(int i=1; i<=n; ++i){
            if(din[i]!=dout[i]){
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }

    // 存在Euler loop的情况
    for(int i=1; i<=n; ++i){
        if(head[i]){dfs(i); break;}
    }

    if(ans.size()!=m){ // 要求整个G是一个Euler loop
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    for(int i=m-1; i>=0; --i) cout<<ans[i]<<" "; // 逆序输出元素

    return 0;
}