分析

• 我们只要清楚如何判断欧拉回路即可。

• 对于无向图，如果所有边连通，且所有点的度数都是偶数则是欧拉回路。

• 对于有向图，如果所有边连通，且所有点的入度等于出度即可。

• 欧拉路径中我们需要对边进行判重，这样时间复杂度会很高。比如某个给定的图只有一个点，但是有很多自环，比如m条自环，然后使用bool数组存储每条边有没有被遍历过。根据上面伪码描述，第一次运行到dfs中会遍历m条边，递归进入dfs后还需要遍历m条边，一共需要遍历m次，因此m个m相加等于$m*m = m^2$，这个时间复杂度很高，本题会超时，因此需要优化。

• 优化的方式是每次遍历过这条边后将其从邻接表中删除，保证之后不会再遍历到这条边。这样就可以保证每条边只会被遍历一次，时间复杂度变为线性。

• 对于无向图，我们在建图的时候加了两条边，因为我们都是成对加入的边，比如（0,1）、（2,3）、…，我们知道一条边的编号是i，则另一条边的编号是i^1，因为无向图每条边也只能被用一次，如果某条边被用过了，另一条边也要标记一下不能使用了。

• 写法参考网址：网址

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 400010;

int type;  // 1代表无向图，2代表有向图
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];  // 记录每条边是否被使用了
int ans[M / 2], cnt;  // 记录欧拉路径
int din[N], dout[N];  // 记录每个点的入度，出度，无向图的度等于入度和出度之和

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {

    while (~h[u]) {  // 这样写是为了跳过应遍历的边
        int i = h[u];  // 当前遍历第i条边

        if (used[i]) {  // 防止无向图的反向边被加入答案中
            h[u] = ne[i];
            continue;
        }

        h[u] = ne[i];  // 这里h[u]被更新，因为h是全局变量，下次dfs就不会遍历到当前考察的边
        // used[i] = true;
        if (type == 1) used[i ^ 1] = true;

        dfs(e[i]);

        if (type == 1) {
            int t = i / 2 + 1;  // 无向图当前考察的是第t条边(从1开始)
            if (i & 1) t *= -1;
            ans[++cnt] = t;
        } else ans[++cnt] = i + 1;
    }
}

int main() {

    scanf("%d", &type);
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (type == 1) add(b, a);
        dout[a]++, din[b]++;  // 一条边只会让两个点的度增加，因此对于无向图也是成立的
    }

    // 判断是否无解
    if (type == 1) {
        for (int i = 1; i <= n; i++)
            if (din[i] + dout[i] & 1) {  // 成立的话说明点i的度为奇数
                puts("NO");
                return 0;
            }
    } else {
        for (int i = 1; i <= n; i++)
            if (din[i] != dout[i]) {
                puts("NO");
                return 0;
            }
    }

    // 求解欧拉路径
    for (int i = 1; i <= n; i++)
        if (~h[i]) {  // 即h[i] != -1
            dfs(i);
            break;  // 只能执行一次dfs函数，否则说明其他边在其他连通分量中
        }

    if (cnt < m) {  // 说明所有边不连通
        puts("NO");
        return 0;
    }

    // 输出答案
    puts("YES");
    for (int i = cnt; i; i--) printf("%d ", ans[i]);
    puts("");

    return 0;
}