跳转至

欧拉图

欧拉路径

对于一个图，走过每条边且仅走过一次的路径，不一定走过每个点。

欧拉回路

起点和终点相同的欧拉路径。

欧拉图

所有边都在同一条欧拉路径上的图。

判定方法

  • 对于有向图，要么所有点的入度都等于出度（存在一个欧拉回路），要么存在且仅存在两个点，一个入度比出度大1，一个出度比入度大1（存在一条不是回路的欧拉路径）。
  • 对于无向图，要么所有点的度数均是偶数（欧拉回路），要么存在且仅存在两个点的度数是奇数，其余均为偶数（一条不是回路的欧拉路径）

实现方法

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

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

例题

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;
}