python/TangDou/AcWing/EulerPath/1124_LJB.cpp

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

const int N = 5e3 + 10, M = N;
typedef pair<int, int> PII;

int n = 500, m;
int ans[M], cnt;
bool st[N];
int d[N];
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
    // 从小到大排序,这是题目中要求的字典序决定的，我们不能按原始的输入序来处理点号，需要全部读取后再由小到大排序
    vector<PII> vec;
    for (int i = h[u]; ~i; i = ne[i]) vec.push_back({e[i], i});
    sort(vec.begin(), vec.end());

    // 捋着点号由小到大的顺序来吧,vector里记录的二元组是 点v，和u->v这条边
    for (int i = 0; i < vec.size(); i++) {
        int j = vec[i].second;
        if (st[j]) continue;
        st[j] = st[j ^ 1] = 1;
        dfs(vec[i].first);
    }
    ans[++cnt] = u;
}
int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b), add(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++;
    // 找到有边连接的点u,本来黄海以为，没有度为奇数的点，那就1号点呗，结果题目中给出的用例居然是10 20
    // 过份了！一共两个点，一个编号为10，另一个编号为20，三营长！你的意大利炮呢！(李云龙只有一营和三营，没有二营)

    // 历尽千辛万苦，终于找到了起点
    dfs(u);

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