跳转至

欧拉路径与欧拉回路

概念

欧拉通路:通过图中所有边恰好一次的通路称为欧拉通路(欧拉路径)。

欧拉回路:通过图中所有边恰好一次的回路称为欧拉回路。

欧拉图:具有欧拉回路的无向图或有向图称为欧拉图。

半欧拉图:具有欧拉通路但不具有欧拉回路的无向图或有向图称为半欧拉图。

Note

有向图也可以有类似的定义。

非形式化地讲，欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

判断方法

  • 对于无向图\(G\)
    • \(G\)是欧拉图(存在欧拉回路)
      • \(G\)是连通的
      • \(G\)所有顶点的度都是偶数
    • \(G\)是半欧拉图(存在欧拉路径,不存在欧拉回路)
      • \(G\)是连通的
      • \(G\)中只有\(0\)个或\(2\)个奇度顶点
  • 对于有向图\(G\)
    • \(G\)是欧拉图
      • 所有顶点属于同一个强连通分量
      • 每个顶点入度和出度相同
    • \(G\)是半欧拉图
      • 退化成无向边时连通
      • 存在顶点\(u\)入度比出度多1
      • 存在顶点\(v\)入度比出度少1
      • 其他顶点入度和出度相同

例1.铲雪车

题目链接

题目描述

随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。

整个城市所有的道路都是双向车道,道路的两个方向均需要铲雪。因为城市预算的削减，整个城市只有 1 辆铲雪车。

铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。

现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？

输入格式

输入数据的第 1 行表示铲雪车的停放坐标 (x,y)，x,y 为整数，单位为米。

下面最多有4000行，每行给出了一条街道的起点坐标和终点坐标，坐标均为整数，所有街道都是笔直的，且都是双向车道。

铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转 U 型弯。

铲雪车铲雪时前进速度为 20 千米/时，不铲雪时前进速度为 50 千米/时。

保证：铲雪车从起点一定可以到达任何街道。

输出格式

输出铲掉所有街道上的雪并且返回出发点的最短时间，精确到分钟，四舍五入到整数。

输出格式为”hours:minutes”，minutes不足两位数时需要补前导零。 具体格式参照样例。

数据范围

\(−10^6≤x,y≤10^6\)

所有位置坐标绝对值不超过 \(10^6。\)

输入样例

1
2
3
4
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

输出样例

1
3:55

样例解释

输出结果表示共需3小时55分钟。

题解

由于是双向图，入度和出度同时增加，因此不存在奇数度的顶点，所以必然存在欧拉回路，因此不管从哪个点开始一定能一笔画回到起点，因此其实答案是固定的，所以只要统计所有路线的长度后计算一下即可，注意时间的转化

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
double get(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
    double x, y;
    double x1, y1, x2, y2;
    double sd = 0;
    cin >> x >> y;
    while(cin >> x1 >> y1 >> x2 >> y2) {
        sd += get(x1, y1, x2, y2) * 2;
    }
    int t = round(sd / 1000 / 20 * 60);
    int hour = t / 60;
    int min = t % 60;
    printf("%d:%02d", hour, min);
    return 0;
}

例2.欧拉回路

题目链接

题目描述

给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

输入格式

第一行包含一个整数 t，t∈{1,2}，如果 t=1，表示所给图为无向图，如果 t=2，表示所给图为有向图。

第二行包含两个整数 n,m，表示图的结点数和边数。

接下来 m 行中，第 i 行两个整数 vi,ui，表示第 i 条边（从 1 开始编号）。

  • 如果 t=1 则表示 vi 到 ui 有一条无向边。
  • 如果 t=2 则表示 vi 到 ui 有一条有向边。

图中可能有重边也可能有自环。

点的编号从 1 到 n。

输出格式

如果无法一笔画出欧拉回路，则输出一行：NO。

否则，输出一行：YES，接下来一行输出 任意一组 合法方案即可。

  • 如果 t=1，输出 m 个整数 p1,p2,…,pm。令 e=|pi|，那么 e 表示经过的第 i 条边的编号。如果 pi 为正数表示从 ve 走到 ue，否则表示从 ue 走到 ve。
  • 如果 t=2，输出 m 个整数 p1,p2,…,pm。其中 pi 表示经过的第 i 条边的编号。

数据范围

\(1≤n≤10^5,\)

\(0≤m≤2×10^5\)

输入样例

1
2
3
4
5
1
3 3
1 2
2 3
1 3

输出样例

1
2
YES
1 2 -3

题解

本题考查有向图和无向图欧拉回路的存在条件以及求法

  • 对于有向图，要求所有顶点入度和出度相等
  • 对于无向图，要求不存在奇数度顶点

可通过上述两点判断是否无解

对于有解情况，我们通过dfs来求得

注意若不进行删边优化的话，复杂度其实是\(O(m^2)\)的

具体删边看代码

我们采取的是先删边再dfs

代码

 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
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 4 * N;

int head[N], e[M], ne[M], idx = 0;
int in[N], out[N]; 
bool vis[M];
int q[M];
int type;
int a, b;
int n, m;
int cnt;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx ++ ;
}

void dfs(int u) {
    for(int &i = head[u]; i != -1;) { 
        // 写成这样的目的是为了边删边遍历，直接删除与head[u]最近的边
        if(vis[i]) {
            i = ne[i]; // 删边
            continue;
        }

        vis[i] = true;
        if(type == 1) vis[i ^ 1] = true; // 如果是无向图，反边也要标记

        int res;
        if(type == 1) {
            res = i / 2 + 1;
            if(i & 1) res = -res;  // 反边
        } else res = i + 1;

        int v = e[i];
        i = ne[i]; // 先删边，在DFS
        dfs(v);
        q[++ cnt] = res; 
    }
}
int main() {
    memset(head, -1, sizeof(head));
    cin >> type >> n >> m;
    for(int i = 1; i <= m; i ++ ) {
        cin >> a >> b;
        add(a, b);
        if(type == 1) {
            add(b, a);
        }

        in[b] ++ ; out[a] ++ ;
    }

    for(int i = 1; i <= n; i ++ ) {
        if(type == 1) {
            if((in[i] + out[i]) & 1) { // 无向图出现奇数度顶点，则不存在欧拉回路
                cout << "NO" << '\n';
                return 0;
            }
        } else {
            if(in[i] != out[i]) { // 有向图出度不等于入度，则不存在欧拉回路
                cout << "NO" << '\n';
                return 0;
            }
        }
    }


    int start = 1;
    while(!(in[start] + out[start]) && start <= n) start ++ ; // 找到第一个有边的点进行dfs

    dfs(start);

    if(cnt < m) { // 如果路径条数没有跑满，说明也是无解
        cout << "NO" << '\n';
        return 0;
    }

    cout << "YES" << '\n';
    for(int i = cnt; i >= 1; i -- ) cout << q[i] << ' ';
    return 0;
}

例3.骑马修栅栏

题目链接

题目描述

农民John每年有很多栅栏要修理。

他总是骑着马穿过每一个栅栏并修复它破损的地方。

John是一个与其他农民一样懒的人。

他讨厌骑马，因此从来不两次经过一个栅栏。

你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。

John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。

每一个栅栏连接两个顶点，顶点用 \(1\) 到 \(500\) 标号(虽然有的农场并没有 \(500\) 个顶点)。

一个顶点上可连接任意多( \(≥1\) )个栅栏。

所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。

我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出\(500\)进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。

输入数据保证至少有一个解。

输入格式

第 \(1\) 行:一个整数 \(F\)，表示栅栏的数目;

第 \(2\) 到 \(F+1\) 行:每行两个整数 \(i,j\) 表示这条栅栏连接 \(i\) 与 \(j\) 号顶点。

输出格式

输出应当有 \(F+1\) 行，每行一个整数，依次表示路径经过的顶点号。

注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

数据范围

\(1≤F≤1024,\)

\(1≤i,j≤500\)

输入样例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

输出样例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
1
2
3
4
2
5
4
6
5
7

题解

本质就是求字典序最小的欧拉路径

对于如何求欧拉路径我们已经清楚了

接下来就是考虑如何让字典序最小

首先很容易想到一个假思路，对于字典序大的翻转以下是否就是字典序小的

但其实这两者并没有本质联系，就比如\(2\ 1\ 2\)和\(1\ 2\ 1\)，无论翻转还是不翻转字典序都是第二个小

我们考虑其他方法

我们发现dfs遍历的过程中，最后遍历到的是最先加入到答案队列中的，这也是为什么当时我们要逆着输出的原因

但是我们遍历边的时候又发现

最先遍历的边其实是最后加入到答案队列的

这样一考虑，岂不是最先遍历到的边在最后最先被输出，因此其实就只需要对每个点能到达的点进行从小到大排序就能让字典序最小

代码

 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
#include<bits/stdc++.h>
using namespace std;

const int N = 505;
int g[N][N];
int in[N], out[N];
int q[1100], cnt;
int maxn = -1;
void dfs(int u) {
    for(int i = 1; i <= maxn; i ++ ) {
        if(g[u][i]) {
            g[u][i] -- ; // 删边
            g[i][u] -- ;
            dfs(i);
        }
    }
    q[++ cnt] = u;  
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ) {
        int a, b;
        cin >> a >> b;
        maxn = max(maxn, a);
        maxn = max(maxn, b);
        g[a][b] ++ ; // 由于有重边，所以不能单单用0,1表示
        g[b][a] ++ ;
        in[b] ++ ;
        out[a] ++ ;
    }

    int root = 1;
    while(!(in[root] + out[root])) root ++ ; //首先从有边的点出发 
    for(int i = 1; i <= maxn; i ++ ) {
        if((in[i] + out[i]) & 1) { // 若有奇度顶点，则从奇度顶点出发
            root = i;
            break;
        }
    }

    dfs(root);
    for(int i = cnt; i >= 1; i -- ) cout << q[i] << '\n'; // 逆着输出
    return 0;
}

例4.单词游戏

题目链接

题目描述

有 \(N\) 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。

你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。

请你编写一个程序，判断是否能达到这一要求。

输入格式

第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。

每组数据第一行包含整数 \(N\)，表示盘子数量。

接下来 \(N\) 行，每行包含一个小写字母字符串，表示一个盘子上的单词。

一个单词可能出现多次。

输出格式

如果存在合法解，则输出”Ordering is possible.”，否则输出”The door cannot be opened.”。

数据范围

\(1≤N≤105,\)

单词长度均不超过\(1000\)

输入样例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

输出样例

1
2
3
The door cannot be opened.
Ordering is possible.
The door cannot be opened.

题解

对于每个单词的首尾字母，我们可以建边

问题就转化为图是否位半欧拉图

我们通过定义判断就行

有向图是半欧拉图条件: + 所有边连通 + 除起点和终点外入度对于出度，或不存在起点和终点

对于条件1我们可以用并查集判断是否连通

代码

 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
#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int in[N], out[N];
int pre[N];
bool vis[N];
int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}
// 有向图存在欧拉路径的条件是1.所有边联通 2.除起点和终点外入度等于出度
int main() {
    int t;
    cin >> t;
    while(t -- ) {
        memset(vis, false, sizeof(vis));
        memset(out, 0, sizeof(out));
        memset(in, 0, sizeof(in));
        int n;
        cin >> n;
        string s;
        for(int i = 0; i < 26; i ++ ) pre[i] = i;
        for(int i = 1; i <= n; i ++ ) {
            cin >> s;
            int a = s[s.size() - 1] - 'a';
            int b = s[0] - 'a';
            vis[a] = vis[b] = true;
            in[b] ++ ;
            out[a] ++ ;
            pre[find(a)] = find(b);
        }

        bool flag = true;
        int st = 0, ed = 0;
        int fa = -1;
        for(int i = 0; i < 26; i ++ ) {
            if(!vis[i]) continue;
            if(fa == -1) fa = find(i);
            else {
                if(find(i) != fa) { // 不在同一个联通块
                    flag = false;
                    break;
                }
            }
            if(in[i] != out[i]) { // 入度不等于出度，则起点终点至多1个
                if(out[i] - in[i] == 1) st ++ ;
                else if(out[i] - in[i] == -1) ed ++ ;
                else {
                    flag = false;
                    break;
                }
            }
        }

        if(!(st == 1 && ed == 1 || st == 0 && ed == 0)) flag = false;

        if(!flag) cout << "The door cannot be opened.\n";
        else cout << "Ordering is possible.\n";
    }

    return 0;
}

参考资料