欧拉回路

前置概念

度数（出度和入度），对于无向图中一点的度数即为与该点相连的边数。

性质

欧拉回路

无向图

每个点的度数均为偶数。可以想象，如果存在欧拉回路则通过一条边进入某个点时，必然需要从另一条边出来，即进入该点的边数与从该点出来的边数相等，即与该点相连的边数为偶数（度数为偶数）。若某无向图中存在度数不为偶数的点，则该无向图不存在欧拉回路。

有向图

每点的入度数等于出度数。与无向图相同，每次从一条边进入则需要从另一条边出来，与之不同的是有向图的边是有向的，所以需要入度数等于出度数。若某有向图中存在入度数不等于出度数的点，则该图不存在欧拉回路。

欧拉路径

欧拉路径相当于把一个欧拉回路从某个点剪开，形成一条路径，所以可以允许存在一个点作为起点，一个点作为终点，这两个点的入度数与出度数的差的绝对值可以为一（起点可以少进入一次，终点可以少出来一次）。

有向图

从起点开始，因此起点可以少进入一次，即起点的入度数可以比出度数少一；到终点即结束，因此终点可以少出来一次，即终点的出度数可以比入度数少一。只能存在两个点（或不存在任何一个点）的入度数与出度数的差的绝对值为一（不能超过一），其中一个（入度数小于出度数）作为起点，另一个（出度数小于入度数）作为终点。否则不存在欧拉路径。

无向图

与有向图相同，起点可以少进入一次，终点可以少出来一次，与有向图不同的是无向图中边是双向的，所以度数为奇数的两个点可以作为起点和终点，若度数为奇数的点为0或2则存在欧拉路径，否则不存在。

思想

深度优先搜索的思想，通过遍历图中的边来找到欧拉回路。

1.选择一个起点，并将其入栈

2.当栈不为空时，从栈顶取出一个顶点，如果该顶点还有未访问的边，则选择一条未访问的边，并将其入栈

3.如果该顶点没有未访问的边，则将该顶点出栈，并将其添加到欧拉回路中

4.重复步骤2和步骤3，直到栈为空。

代码实现

欧拉回路

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int book[N][N];
int idn[N], out[N];
vector<int> ans;
void dfs(int x, int n) {
    for (int i = 1; i <= n; i++) {
        //可能存在两个点之间存在多条边
        if (book[x][i] > 0) {
            book[x][i]--;
            //无向图
            book[i][x]--;
            dfs(i, n);
        }
    }
    //存入路径
    ans.push_back(x);
}
signed main() {
    int n, m;
    cin>>n>>m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin>>u>>v;
        book[u][v]++;
        idn[u]++;
        out[v]++;
        //无向图
        book[v][u]++;
        idn[v]++;
        out[u]++;
    }
    for (int i = 1; i <= n; i++) {
        if (idn[i] & 1) {
            cout<<"不存在欧拉回路";
            return 0;
        }
    }
    //这里从点1开始，因为是欧拉回路，所以其实从哪个点开始都可以
    dfs(1, n);
    int len = ans.size();
    for (int i = len - 1; i >= 0; i--) {
        //逆向输出
        cout<<ans[i]<<" ";
    }
    return 0;
}

欧拉路径

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 const int N = 1e3 + 5;
 5 int book[N][N];
 6 int idn[N], out[N];
 7 vector<int> ans;
 8 void dfs(int x, int n) {
 9     for (int i = 1; i <= n; i++) {
10         //可能存在两个点之间存在多条边
11         if (book[x][i] > 0) {
12             book[x][i]--;
13             //无向图
14             book[i][x]--;
15             dfs(i, n);
16         }
17     }
18     //存入路径
19     ans.push_back(x);
20 }
21 signed main() {
22     int n, m;
23     cin>>n>>m;
24     for (int i = 1; i <= m; i++) {
25         int u, v;
26         cin>>u>>v;
27         book[u][v]++;
28         idn[u]++;
29         out[v]++;
30         //无向图
31         book[v][u]++;
32         idn[v]++;
33         out[u]++;
34     }
35     int head = 0;
36     int cnt = 0;
37     //查找度数为奇数点的个数
38     for (int i = 1; i <= n; i++) {
39         if (idn[i] & 1) {
40             cnt++;
41             //一般会要求按字典序输出，所以找到第一个度数为奇数的作为起点
42             if (head == 0)
43                 head = i;
44         }
45     }
46     if (cnt != 0 && cnt != 2) {
47         cout<<"不存在欧拉路径";
48         return 0;
49     }
50     //全为偶数则可以把任何一个点作为起点
51     if (head == 0)
52         head = 1;
53     dfs(head, n);
54     int len = ans.size();
55     for (int i = len - 1; i >= 0; i--) {
56         //逆向输出
57         cout<<ans[i]<<" ";
58     }
59     return 0;
60 }