小指针

V1

2022/10/09阅读:24主题:凝夜紫

【图论专题】欧拉路径和欧拉回路问题

欧拉路径和欧拉回路

哥尼斯堡七桥问题:18世纪初普鲁士的哥尼斯堡,有一条河穿过,河上有两个小岛,有七座桥把两个岛与河岸联系起来(如概述图)。有个人提出一个问题:一个步行者怎样才能不重复、不遗漏地一次走完七座桥,最后回到出发点。后来大数学家欧拉把它转化成一个几何问题——一笔画问题

在图论的概念里,我们把这个一笔画问题称为欧拉路径问题

欧拉路径问题:是否存在一个路劲,使得每条边 恰好 走一次

欧拉回路问题:是否存在一个环路,使得每条边 恰好 走一次

欧拉路径和欧拉回路的成立条件

我们先把七桥问题转换成,于是可以得到如下图:

我们发现四个点的度分别是:3、3、5、3

我们发现对于起点的度来说,从起点初始延伸出一条出边,而后其他的边再经过起点,必定是进去之后还要出来,也就是度一定是偶数,那么算上起点初始延伸出去的那条边,最终起点的度一定是奇数

而对于终点的度来说,除了最终走到它的那条边之外,其他所有经过它的边,必定也是进去之后再出来,所以同起点的度一样,终点的度也一定是奇数

对于路径中所有中间点的度来说,走进来之后一定就要走出来,所以中间点的度 一定是偶数

因此,我们就能得出一些关于欧拉路径问题的结论

对于无向图来说:

  1. 欧拉路径问题成立的充分必要条件:度数为奇数的点只能有0个或者2个

  2. 欧拉回路问题成立的充分必要条件:我们把欧拉回路看成是一种特殊的欧拉路径,因为起点也是终点,所以起点的度也必须是偶数。于是得到结论度数为奇数的点只能有0个

对于有向图(所有边都连通)来说:

  1. 存在欧拉函数的充分必要条件:要么所有点的出度均等于入度;要么除了两个点之外,其余所有点的出度等于入度。剩余的两个点,起点满足出度比入度多1,终点满足入度比出度多1

  2. 存在欧拉回路的充分必要条件:所有点的出度都等于入度

基础思路

int seq[N]; // 存储最终的路径序列
void dfs(u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        dfs(e[i]); // 扩展
    }
    把u加入序列  seq[]←u
}

最后,seq[]中存下的就是欧拉路径的倒序

AcWing 1123. 铲雪车

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

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

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

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

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

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

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

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

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

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

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

数据范围

−10^6≤x,y≤10^6
所有位置坐标绝对值不超过 10^6。

输入样例

0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

输出样例

3:55

样例解释

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

题目描述

一个城市铲雪的问题,这个城市因为预算只有一辆铲雪车啦(可以说是非常穷了)。

一个城市有很多双向道路,铲雪车从一个起点开始沿着道路走,所有它走过的地方会被铲掉,因为是双向道路,所以两个方向均需要铲雪,铲雪车需要过去一趟,回来一趟,才能铲完一条道路上的雪。铲雪车在任意街道的末尾或者交叉口,可以随意转向,问题是最少需要多少时间可以铲除所有道路上的雪

题目分析

我们以图中点b为参照点,可以发现,因为每条道路都是双向的,也就是说,假如另一个到达b的点是a,那么a->b会为b提供一个入度,而b->a会为b提供一个出度,也就是说对于点b来说,有一个出度就会有一个入度,它的出入度永远是成对出现的,也就是说永远不可能出现单数(奇数)

进而,我们发现其实任意一个点都满足上面得出来的结论:所有点的度都不是奇数,说明题目给出的图,其实是一个欧拉回路,那么我们就一定有办法,每条路都只走一遍(一个来回),就可以铲完所有雪

也就是二倍的所有路径总长度 除以 铲雪速度

所以,本题虽然是个图论问题,但是更向一个脑筋急转弯,我们用欧拉回路的性质,可以直接算出来结果。

Code

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int main() {
    double x1, y1,  x2, y2;
    cin >> x1 >> y1;
    double sum = 0;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        sum += sqrt(dx * dx + dy * dy) * 2;
    }
    // 转换成千米 除以速度 再转换成小时 round是四舍五入
    int minutes = round(sum / 1000 / 20 * 60); 
    int hours = minutes / 60;
    minutes %= 60;
    printf("%d:%02d\n", hours, minutes);
    return 0;
}

AcWing 1184. 欧拉回路

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

输入格式
第一行包含一个整数 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≤105,
0≤m≤2×105

输入样例1

1 3 3 1 2 2 3 1 3 输出样例1

YES
1 2 -3

输入样例2

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

输出样例2

YES
4 1 3 5 2 6

题目描述

纯粹的欧拉回路模板题

题目分析

纯粹的欧拉回路模板题

有一个需要特别考虑的问题是如何判断无解,我们可以根据性质定义来判断是否有解。

对于无向图来说,有解的话:

  1. 所有点的度数必须是偶数;
  2. 所有边必须都是连通的;

对于有向图来说,有解的话:

  1. 所有点的入度等于出度;
  2. 所有边连通;

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010;
int n, m, type;
int h[N], e[M], ne[M], idx;
// 欧拉回路每条边只能使用一次
bool used[M]; // 判断每条边是否使用过
int ans[M], cnt; // 记录路径和路径的长度
int din[N], dout[N];

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

void dfs(int u) {
    for (int &i = h[u]; ~i;) {
        if (used[i]) {
            // 边已经被用过则删掉一条边
            i = ne[i];
            continue;
        }
        used[i] = true// 标记边 u->i 已经被用过了
        // 马上就要用这条边 也把它删掉
        // 如果是无向图 同时标记反向边也被用掉了。
        if (type == 1) used[i ^ 1] = true;
        int t;
        // 把当前边添加到结果
        if (type == 1) {
            // (0,1) (2,3) (4,5) 奇数作为返回的边
            t = i / 2 + 1;
            // 边从0开始计数  所以当i为奇数的时候是反向边
            if (i & 1) t = -t;
        } else t = i + 1;
        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[ ++ cnt] = t;
    }
}

int main() {
    cin >> type;
    cin >> n >> m;
    memset(h, -1sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        if (type == 1) add(b, a);
        din[b] ++, dout[a] ++ ;
    }
    if (type == 1) {
        // 如果是无向图 那么每个点的度 必须是偶数
        for(int i = 1; i <= n; i ++ ) {
            if (din[i] + dout[i] & 1) {
                puts("NO");
                return 0;
            }
        }
    } else {
        // 如果是有向图 那么每个点的入度则必须等于出度
        for (int i = 1; i <= n; i ++ ) {
            if (din[i] != dout[i]) {
                puts("NO");
                return 0;
            }
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        // 找到一个存在边的点 作为起点
        if (h[i] != -1) {
            dfs(i);
            break;
        }
    }
    // 最后的路径如果没有走过所有的边 也失败
    if (cnt < m) { 
        puts("NO");
        return 0;
    }
    puts("YES");
    for (int i = cnt; i > 0; i -- ) printf("%d ", ans[i]);
    puts("");
    return 0;
}

AcWing 1124. 骑马修栅栏

农民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

输入样例

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

输出样例

1
2
3
4
2
5
4
6
5
7

题目描述

有很多相互连接的栅栏,一个要走过所有的栅栏,但是每个栅栏它不想走两次,最后输出字典序最小的可行的路径

也就是给出一个无向图,求字典序最小的欧拉路径。

题目分析

本题主要的难点在于求字典序最小

我们在求欧拉路径的时候,是在自底向上的递归,也就是说先遍历到的点会后加入到路径序列,所以我们只需要保证当前点的所有出边 是 从小到大排序就可以。

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;
// 数据未给出点数量,但是题目中有说最多500个点
int n = 500, m;
// 需要从小到大搜索 邻接表比较麻烦 所以用邻接矩阵存图
int g[N][N]; 
int ans[1100], cnt;
int d[N];

void dfs(int u) {
    for (int i = 1; i <= n; i ++ ) {
        if (g[u][i]) {
            // 欧拉路径 每条边只能用一次 
            // 所以用完就删掉这条无向边
            g[u][i] --, g[i][u] --;
            dfs(i);
        }
    }
    ans[++ cnt] = u; // 加入序列
}

int main() {
    cin >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        g[a][b] ++, g[b][a] ++ ; // 无向图
        d[a] ++ , d[b] ++ ;
    }
    int start = 1// 找一个起点
    // 找到较小的有度数的编号作为起点
    while (!d[start]) start ++ ; 
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] % 2) {
            start = i; // 较小的奇数点作为起点
            break;
        }
    }
    dfs(start);
    // 因为序列中是反的 所以输出时候也要反向输出结果
    for (int i = cnt; i; i -- ) printf("%d\n", ans[i]);
    return 0;
}

AcWing 1185. 单词游戏

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

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

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

输入格式
第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含整数 N,表示盘子数量。

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

一个单词可能出现多次。

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

数据范围

1≤N≤105,
单词长度均不超过1000

输入样例

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

输出样例

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

题目描述

有N个盘子,每个盘子上有一个单词,单词首尾可以拼接,需要我们判断是否可以把所有的单词都拼接到一起。

题目分析

假设把单词看做一条边26个小写英文字母看做点,那么问题就是能否找到一条路径 依次走过每条边。也就是判断有向图是否存在欧拉路径

有向图的欧拉路径判断:

  1. 除了起点和终点外,其余点入度等于出度;
  2. 是否整个图都连通;

Code

实现上,判断图是否连通可以使用并查集

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30// 26个字母
int n, m;
int din[N], dout[N], p[N];
bool st[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    char str[1010];
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        memset(st, 0sizeof st);
        memset(din, 0sizeof din);
        memset(dout, 0sizeof dout);
        for (int i = 0; i < 26; i ++ ) p[i] = i;
        
        for (int i = 0; i < n; i ++ ) {
            scanf("%s", str);
            int len = strlen(str);
            int a = str[0] - 'a', b = str[len - 1] - 'a';
            st[a] = st[b] = true// ab已经被使用
            dout[a] ++ , din[b] ++ ;
            p[find(a)] = find(b);
        }
        int start = 0, end = 0// 首尾节点
        bool flag = true// 判断是否成功
        // 找到首尾节点
        for (int i = 0; i < 26; i ++ ) {
            // 只有首尾节点可以入度出度不同
            if (din[i] != dout[i]) { 
                // 尾节点入度多1 首节点出度多1
                if (din[i] == dout[i] + 1) end ++ ;
                else if (din[i] + 1 == dout[i]) start ++ ;
                // 不是首尾节点 入度出度不同 则说明不是欧拉路径
                else {
                    flag = false;
                    break;
                }
            }
        }
        // 如果找到首尾节点 也需满足条件(见分析)才可以
        // if (flag and !((!start and !end) or (start == 1 and end == 1))) flag = false;
        if (flag && !(!start && !end || start == 1 && end == 1)) flag = false;
        // 还需要判断连通性
        int rep = -1;
        for (int i = 0; i < 26; i ++ ) {
            if (st[i]) {
                if (rep == -1) rep = find(i); // 找唯一祖宗节点
                else if (rep != find(i)) {  // 有点不属于同一个集合则不连通
                    flag = false;
                    break;
                }
            }
        }
        if (flag) puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
    return 0;
}

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1