Consolexin's blog
consolexinhun
2021-10-19
目录

欧拉图

# 欧拉回路和欧拉通路

# 定义

欧拉通路：所有边经过且只经过一次

欧拉回路：所有边经过且只经过一次，回到出发点

# 性质

无向图欧拉通路：

1、连通图并且有两个奇点或者没有奇点

2、如果连通图有两个奇点，那么欧拉通路必定以两个奇点为端点

3、如果连通图没有奇点，那么必然有欧拉回路

有向图欧拉通路：

判定条件：

情况一：基图连通，并且所有顶点的入度和出度相等

情况二：基图连通，除两个顶点外，其余点的出度和入度相等，且这两点中，一个出度和入度差为 1，另一个为 -1

推论：

1、欧拉通路必定以出度入度之差为 1 的顶点作为起始点，以出度入度之差为 -1 的顶点作为终点

2、所有顶点出度入度相等时，必定有欧拉回路

# 欧拉通路和回路判断

判断欧拉通路是否存在：

有向图：连通，一个顶点出度比入度大 1，另一个顶点入度比出度大 1，其余点出度等于入度

无向图：图连通，只有两个奇点，其余都是偶点

判断欧拉回路是否存在：

有向图：连通，所有点出度等于入度

无向图：连通，所有点是偶点

# 题目

# LC0332 重新安排行程

有向图欧拉回路

https://leetcode-cn.com/problems/reconstruct-itinerary

必定存在一个欧拉回路或者欧拉通路，找到字典序最小的路径

# DFS 解法

class Solution {

private:
    vector<string> result; // 记录遍历的结果
    unordered_map<string, map<string, int>> u; // 某机场能到达的机场，并且记录应该到达几次
public:
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto it: tickets){
            u[it[0]][it[1]]++;
        }
        result.push_back("JFK");

        int n = tickets.size(); // 航班数量 
        dfs(n);

        return result;
    }

    bool dfs(int n){
        if(result.size() == n+1) { // 到达的机场数 等于 航班数+1，结束
            return true;
        }

        for(auto &it: u[result[result.size()-1]]){
            if(it.second > 0){
                it.second--;
                result.push_back(it.first);

                if(dfs(n)) return true;

                it.second++;
                result.pop_back();
            }
        }

        return false;
    }


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

# hierholzer 解法

提示

图中最多存在一个死胡同，并且这个死胡同最后访问到，否则不能完成一笔画，因此最先加入到栈中，最后输出栈中的结果。

DFS 就是拆边，每次递归删除一条边，所有子递归返回后将当前点加入结果集，递归到死胡同后递归函数返回。

class Solution {

private:
    unordered_map<string, vector<string>> u;
    vector<string> res;

public:
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto it: tickets){
            u[it[0]].push_back(it[1]);
        }

        for(auto &it: u){
            sort(it.second.begin(), it.second.end());
        }

        int n = tickets.size();
        dfs("JFK", n);

        reverse(res.begin(), res.end());
        return res;
    }

    void dfs(string a, int n){
        while(u[a].size() > 0){
            string k = u[a][0];

            u[a].erase(u[a].begin());

            dfs(k, n);

            res.push_back(a);
        }

        if(res.empty()){  // 这是为了将最后遍历的那个节点加进去
            res.push_back(a);
        }
    }
};
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

另一种写法，加入到结果放在外面

class Solution {

private:
    unordered_map<string, vector<string>> u;
    vector<string> res;
public:
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto it: tickets){
            u[it[0]].push_back(it[1]);
        }

        for(auto &it: u){
            sort(it.second.begin(), it.second.end());
        }

        dfs("JFK");

        reverse(res.begin(), res.end());
        return res;
    }

    void dfs(string a){
        while(u[a].size() > 0){
            string k = u[a][0];

            u[a].erase(u[a].begin());

            dfs(k);
        }
        res.push_back(a);
    }
};
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

# 洛谷 2731 骑马修栅栏

无向图欧拉回路，并且是整数

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

//
// Created by Administrator on 2021/10/19.
//

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;


const int N = 501;
int u[N][N]; // 邻接矩阵建图
unordered_map<int, int> cnt; // 记录每个点出现的次数
vector<int> v; // 记录最终结果，其实是个栈，最后反序就行

int maxn = 0;  // 图上有几个点

void init(){
    memset(u, 0, sizeof(u));
    cnt.clear();
    v.clear();
}

void dfs(int n){
    for(int i = 1; i <= maxn; i++){ // 判断当前点接下来要到哪个点
        if(u[n][i] > 0){
            // 由于是无向图，走了 n 到 i，那么 i 到 n 也要减少
            u[n][i]--;
            u[i][n]--;

            dfs(i);
        }
    }
    v.push_back(n);
}

int main(){
    int m;
    scanf("%d", &m);

    init();

    int a, b;
    for(int k = 0; k < m; k++){
        scanf("%d %d", &a, &b);
        u[a][b]++;
        u[b][a]++;
        cnt[a]++;
        cnt[b]++;

        maxn = max({maxn, a, b});
    }

    bool isOdd = false;
    int minOdd = 0x3f3f3f3f, minEven = 0x3f3f3f3f;
    // 寻找有没有奇点，并且找到最小的奇点和偶点
    for(pair<int, int> t: cnt){
        if(t.second & 1){
            isOdd = true;
            if (t.first < minOdd) minOdd = t.first;
        }
        if(t.first < minEven) minEven = t.first;
    }

    if(isOdd){
        dfs(minOdd);
    }else{
        dfs(minEven);
    }

    reverse(v.begin(), v.end());
    for(int l: v) printf("%d\n", l);

    return 0;
}
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
68
69
70
71
72
73
74
75
76
77
78
79
80

# 洛谷 1341 无序字母对

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

将字母转数字，同样也是无向图的欧拉路径

步骤：

1、判断图是否连通，用并查集，所有点的父亲只能有一个

2、判断奇点个数，只能是 0 个或者 2 个

3、从最小点遍历，用 Hierholzer 算法求欧拉路径

//
// Created by Administrator on 2021/10/19.
//

#include<vector>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>

using namespace std;

const int N = 128+1;

int m[N][N];
vector<int>v;
int cnt[N];

int f[N];

int find(int n){
    return f[n] == n ? n : find(f[n]);
}

void init(){
    memset(m, 0, sizeof(m));
    memset(cnt, 0, sizeof(cnt));
    v.clear();

    for(int i = 0; i < N; i++) f[i] = i;
}


void dfs(int n){
    for(int i = 1; i < N; i++){
        if(cnt[n] && m[n][i] > 0){
            m[n][i]--;
            m[i][n]--;

            dfs(i);
        }
    }
    v.push_back(n);
}

int main(){
    init();

    int n;
    scanf("%d", &n);

    string s;
    while(n--){
        cin>>s;
        int a = s[0]-'A'+1, b = s[1]-'A'+1;
        m[a][b]++;
        m[b][a]++;

        cnt[a]++;
        cnt[b]++;

        f[find(a)] = find(b);
    }


    // 判断图是否连通，也就是对于存在的字母，只有一个父亲
    int res = 0;
    for(int i = 1; i < N ; i++) if(cnt[i] && find(i) == i) res++;

    if(res != 1) {
        puts("No Solution");
        return 0;
    }

    // 计算图的奇点数目，最小奇点，最小偶点
    int oddNum = 0, minOdd = 0x3f3f3f3f, minEven = 0x3f3f3f3f;
    bool isOdd = false;
    for(int i = 0; i < N; i++){
        if(cnt[i]){
            if(cnt[i] & 1){
                isOdd = true;
                oddNum++;

                minOdd = min(minOdd, i);
            }

            minEven = min(minEven, i);
        }
    }
    if(!(oddNum == 0 || oddNum == 2)) {  // 奇点个数或者0或者2
        puts("No Solution");
        return 0;
    }

    if(isOdd){
        dfs(minOdd);
    }else{
        dfs(minEven);
    }

    reverse(v.begin(), v.end());
    for(int k: v){
        printf("%c", k-1+'A');
    }
    puts("");

    return 0;
}
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

参考链接：

欧拉回路遍历注意事项： (opens new window)

欧拉回路基本概念+判断+求解： (opens new window)

OI WIKI (opens new window)

编辑 (opens new window)
#图论
上次更新: 2025/05/21, 06:42:57
单源最短路
拓扑排序

← 拓扑排序→

最近更新
01
6-其他操作
05-20
02
4-联结
05-20
03
7-管理
05-20
更多文章>
Theme by Vdoing | Copyright © 2019-2025 Consolexinhun | MIT License
×