PP4880 欧拉回路（提高）

欧拉回路是一道非常经典的图论题目，可以把它想象成"一笔画"游戏：从起点出发，每条边恰好经过一次，最后又回到起点，这样走出来的封闭路线就是欧拉回路。

解题思路

第一步，认识欧拉回路。 题目要求输出从结点 1 开始的一条欧拉回路，并且回路上结点的编号要尽量小。比如样例中 1-2-4-5-6-4-3-1 就是一条欧拉回路：它从 1 出发，把 7 条边各走一遍，最后回到 1。

第二步，判断是否存在欧拉回路。 数学家欧拉发现了一个很简单的规律：一个无向连通图存在欧拉回路，当且仅当每个结点的度数都是偶数。结点的度数就是和它相连的边数。为什么必须全是偶数呢？因为回路每"路过"一个结点一次，就要用掉一条进去的边和一条出去的边，边一对一对地被消耗，所以度数只能成双成对。我先统计每个结点的度数，只要出现一个奇数度结点，就直接输出 "no oula circle"。

第三步，用深度优先搜索找回路。 从结点 1 出发做 DFS。每次走到一个结点 u，就挑一条还没用过的边走到下一个结点 v。为了让回路"优先编号小"，我总是先尝试编号小的邻居。用邻接矩阵 a[u][v] 记录 u 和 v 之间还剩几条边，走一条边就把 a[u][v] 和 a[v][u] 都减 1，这样每条边只会被用一次。当所有边都走完后，递归回溯时把结点依次存进 path 数组。

第四步，把记录逆序输出。 DFS 过程中记录的顺序是"走完某条路之后"的倒序，所以最后把 path 从后往前输出，正好是从 1 开始的一条欧拉回路。例如样例经过计算，逆序输出就是 1 2 4 5 6 4 3 1，和标准答案一致。

第五步，注意细节。 度数数组要用 int 统计，矩阵要开得比 n 稍大一点防止越界；如果图里恰好所有结点度数都是偶数，就一定能走出回路。这道题评测数据保证是连通图，所以只需要判断度数这一个条件即可。

参考代码

// 判断无向连通图是否存在欧拉回路，存在则输出从1开始字典序最小的回路
#include <iostream>
using namespace std;

int a[505][505]; // 邻接矩阵，记录两点间剩余边数
int path[200005]; // 保存回路结点（递归收集）
int n, m, top;

void dfs(int u) {
    for (int v = 1; v <= n; v++) { // 按编号从小到大找边，保证字典序最小
        if (a[u][v] > 0) {
            a[u][v]--;
            a[v][u]--; // 无向边两个方向都消耗
            dfs(v);
        }
    }
    path[++top] = u; // 回溯时记录
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y]++;
        a[y][x]++;
    }
    // 欧拉回路要求每个顶点度数为偶数
    for (int i = 1; i <= n; i++) {
        int deg = 0;
        for (int j = 1; j <= n; j++) deg += a[i][j];
        if (deg % 2 != 0) {
            cout << "no oula circle" << endl;
            return 0;
        }
    }
    dfs(1);
    // 逆序输出得到从1开始的欧拉回路
    for (int i = top; i >= 1; i--) {
        if (i < top) cout << " ";
        cout << path[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

复杂度分析：判断度数需要遍历邻接矩阵，DFS 找回路时每个结点最多扫描所有邻居，总时间复杂度 O(n²)，其中 n 是结点数；空间上邻接矩阵占 O(n²)，路径数组占 O(m)，m 是边数。题目数据规模不大，这个复杂度完全够用。