欧拉回路

定义

欧拉通路：能一次性走完一张图上所有的边，且每条边只经过一次
欧拉回路：能一次性走完一张图上所有的边，每条边只经过一次，且这条路径构成一个回路（即最终回到了出发点）

欧拉回路必须满足的条件：

无向图：度数为奇数的点的个数 == 0 或者 == 2（== 0 ： 欧拉回路， == 2 ：欧拉通路）

有向图：除了起点和终点，每个点的入度 == 出度，满足 起点的出度-入度 == 1 && 终点入度-出度 == 1 或者 起点终点为同一个

思路

dfs。

首先需要确定dfs的起点，这可以通过输入边时统计度数实现，如果奇数度数的点不是0或2，则无欧拉通路；有两个奇数点的，找到其中一个点作为起点；度数全为偶数的，任意指定一个点作为起点。

然后开始dfs，每经过一条路时就把它的次数--，免得重复经过，当无路可走时，就存下当前的点（注意是逆序），回溯，继续遍历

模版题

https://www.luogu.com.cn/problem/P2731

code

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 500 + 10;
int m, n = 500, u, v;
int rd[N], path[N][N];
int start = 1;
int cnt, ans[N];

void dfs(int u) {
    for(int i = 1; i <= 500; i++) {
        if(path[u][i]) {
            path[u][i]--;
            path[i][u]--;  //  有向图删掉
            dfs(i);
        }
    }
    ans[++cnt] = u;
}

int main() {  
    ios::sync_with_stdio(false);
    cin >> m;
    for(int i = 1; i <= m; i++) {
        cin >> u >> v;
        path[u][v]++; path[v][u]++;
        rd[u]++; rd[v]++;
    }
    for(int i = 1; i <= 500; i++) {
        if(rd[i] % 2) {
            start = i;
            break;
        }
    }
    dfs(start);
    for(int i = cnt; i >= 1; i--) cout << ans[i] << endl;
    return 0;
}