欧拉回路

欧拉回路的条件之类的就不赘述了，这里主要说一下这道题的一些细节部分。

首先是题目要求输出的编号。我看很多题解都用了很麻烦的链式前向星加边后用地址算边的编号…其实只需要在加边的时候令边权为编号即可，无向图的反相边就令边权为负，这样就可以省去很多不必要的算编号的过程。其次是虽然可以使用数组判断边是否走过，但很多时候会产生很多重复判断，导致最后结果超时。这个时候如果使用链式前向星，则可在遍历的时候令保存链表头结点的数组不断改为当前遍历到的点，即可快速删除已经走过的边，达到优化的目的。

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
struct node{
    int u,v,w,next;
}a[M];
int f[N],cnt;
void add(int u,int v,int w){
    a[++cnt].v = v;
    a[cnt].w = w;
    a[cnt].next = f[u];
    f[u] = cnt;
}
vector<int> ans;
int vis[M],in[N],out[N];
void dfs(int u){
    //使用引用，使得每次i在指到下一边的时候更新头结点数组达到删边效果
    for(int &i = f[u];i;i = a[i].next){
        int v = a[i].v,w = a[i].w;
        //虽然进行了删边，但由于无向图反相边的存在需要进行判断
        if(vis[abs(w)]) continue;
        vis[abs(w)] = 1;
        dfs(v);
        ans.push_back(w);
    }
}
int main(){
    int t,n,m;
    cin>>t;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v, i);
        in[u]++;out[v]++;
        if(t==1) {
            add(v, u, -i);
            in[v]++;
        }
    }
    for(int i = 1;i<=n;i++){
        if(t==1&&in[i]%2||t==2&&in[i]!=out[i]){
            puts("NO");
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        if(f[i])   {
            dfs(i);break;
        }
    }
    int len = ans.size();
    if(len!=m) {
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int i = len-1;i>=0;i--) printf("%d ",ans[i]);
    return 0;
}