小指针
2022/10/09阅读：165主题：凝夜紫
【图论专题】欧拉路径和欧拉回路问题
欧拉路径和欧拉回路
「哥尼斯堡七桥问题」：18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如概述图）。有个人提出一个问题：「一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点」。后来大数学家欧拉把它转化成一个几何问题——「一笔画问题」。
在图论的概念里，我们把这个「一笔画问题」称为「欧拉路径问题」。
「欧拉路径问题」：是否存在一个「路劲」，使得「每条边 恰好 走一次」。
「欧拉回路问题」：是否存在一个「环路」，使得「每条边 恰好 走一次」。
欧拉路径和欧拉回路的成立条件
我们先把「七桥问题」转换成「图」，于是可以得到如下图： 
我们发现「四个点的度」分别是：3、3、5、3。
我们发现对于起点的度来说，从「起点初始延伸出一条出边」，而后其他的边「再经过起点」，必定是「进去之后还要出来」，也就是「度一定是偶数」，那么算上起点初始延伸出去的那条边，最终「起点的度一定是奇数」。
而对于终点的度来说，除了最终走到它的那条边之外，其他所有经过它的边，必定也是「进去之后再出来」，所以同起点的度一样，「终点的度也一定是奇数」。
对于路径中所有中间点的度来说，「走进来之后一定就要走出来」，所以「中间点的度 一定是偶数」。
因此，我们就能得出一些关于「欧拉路径问题的结论」：
对于无向图来说：
欧拉路径问题成立的充分必要条件：「度数为奇数的点只能有0个或者2个」；
欧拉回路问题成立的充分必要条件：我们把欧拉回路看成是一种特殊的欧拉路径，因为起点也是终点，所以起点的度也必须是偶数。于是得到结论「度数为奇数的点只能有0个」；
对于有向图（所有边都连通）来说：
存在欧拉函数的充分必要条件：要么「所有点的出度均等于入度」；要么「除了两个点之外，其余所有点的出度等于入度」。剩余的两个点，「起点满足出度比入度多1，终点满足入度比出度多1」。
「存在欧拉回路」的充分必要条件：「所有点的出度都等于入度」。
基础思路
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
题目描述
纯粹的「欧拉回路模板题」。
题目分析
纯粹的「欧拉回路模板题」。
有一个需要特别考虑的问题是「如何判断无解」，我们可以根据性质定义来判断是否有解。
对于无向图来说，有解的话：
-
所有点的度数必须是偶数； -
所有边必须都是连通的；
对于有向图来说，有解的话：
-
所有点的入度等于出度； -
所有边连通；
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, -1, sizeof 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个小写英文字母看做点」，那么问题就是「能否找到一条路径 依次走过每条边」。也就是判断「有向图」是否存在「欧拉路径」。
有向图的欧拉路径判断：
-
除了起点和终点外，其余点入度等于出度； -
是否整个图都连通；
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, 0, sizeof st);
memset(din, 0, sizeof din);
memset(dout, 0, sizeof 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」
作者介绍