跳转至

欧拉图

  • 欧拉路径：恰好经过每条边一次；
  • 欧拉回路：起点和终点相同的欧拉路径；
  • 欧拉图：存在一条欧拉路径的图；

欧拉图的判定

  • 对于有向图 \(G=(V,E)\)，当且仅当 \(\forall u\in V,\ deg_{in}(u)=deg_{out}(u)\)，图存在欧拉回路；
  • 对于无向图 \(G=(V,E)\)，当且仅当 \(\forall u\in V,\ 2\mid deg(u)\)，图存在欧拉回路；

对于欧拉路径，我们可以将其视为一个欧拉回路去掉一条边。因此，有向图存在欧拉路径的条件是仅两个点入度和出度相差 \(1\)，无向图存在欧拉路径的条件是仅两个点度数为奇数。这两个点就分别是起点和终点。

寻找欧拉路径和欧拉回路

  • 访问到点 \(u\)；
  • 遍历其所有没有访问过的出边 \((u,v)\)；
  • 标记 \((u,v)\) 为访问过；
  • 递归访问 \(v\)；
  • 将当前点入栈；

将栈中元素依次弹出，即得一条欧拉路径（回路）

P7771 【模板】欧拉路径

因为题目中要求输出字典序最小的欧拉回路，因此选择编号最小的点作为起点，通过排序使其总是先访问编号较小的点。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1E5 + 10;

int n, m;
vector<int> adj[N];
int cur[N];

int ind[N], otd[N];

int sta[N], top;
void dfs(int u) {
    for(int i = cur[u]; i < (int)adj[u].size(); i = max(i + 1, cur[u])) {
        cur[u]++;
        dfs(adj[u][i]);
    }
    sta[++top] = u;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        ind[v]++;
        otd[u]++;
    }

    for(int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
    }

    bool flag = true;
    int beg = 0, end = 0;
    for(int i = 1; i <= n; i++) {
        if(ind[i] != otd[i]) flag = false;
        if(ind[i] == otd[i] + 1) {
            if(end != 0) end = -1;
            else end = i;
        } else if(ind[i] + 1 == otd[i]) {
            if(beg != 0) beg = -1;
            else beg = i;
        } else if(ind[i] != otd[i]) {
            beg = end = -1;
        }
    }

    if(!flag && !(beg > 0 && end > 0)) {
        cout << "No" << endl;
        return 0;
    }

    if(flag) beg = 1;

    dfs(beg);

    while(top > 0) {
        cout << sta[top--] << ' ';
    }
    cout << endl;

    return 0;
}