python/TangDou/AcWing/EulerPath/1124.cpp

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

const int N = 510, M = N * N;

int n = 500, m;  // n个点，m条边
int g[N][N];     // 邻接矩阵存图
int ans[M], cnt; // 路径
int d[N];        // 度

void dfs(int u) {
    // 因为最后的欧拉路径的序列是ans数组逆序，
    // 节点u只有在遍历完所有边之后最后才会加到ans数组里面，所以逆序过来就是最小的字典序
    for (int i = 1; i <= n; i++)
        if (g[u][i]) {
            // 删边优化
            g[u][i]--, g[i][u]--;
            dfs(i);
        }
    ans[++cnt] = u;
}

int main() {
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        g[a][b]++, g[b][a]++; // 无向边，可记录重边
        d[a]++, d[b]++;       // 记录度
    }

    // 找起点
    int u = 0;
    // ① 从小到大，找到度为奇数的点，在无向图中，度为奇数的点，视为起点
    for (int i = 1; i <= n; i++)
        if (d[i] & 1) {
            u = i;
            break;
        }

    // ② 如果没有找到度为奇数的点，可能就是一个环，也就是欧拉回路
    if (!u)
        while (!d[u]) u++;

    dfs(u);

    for (int i = cnt; i; i--) printf("%d\n", ans[i]);

    return 0;
}