图论——欧拉回路和欧拉路径_欧拉回路的充要条件

欧拉回路与欧拉路径

给定一张无向图，若存在一条从节点$S$到节点$T$的路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，则称该路径为$S$到$T$的欧拉路。
特别地，若存在一条从节点$S$出发地路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，最终回到起点$S$,则称该路径为欧拉回路，存在欧拉回路的无向图被称为欧拉图。

一、无向图
1 存在欧拉路径的充要条件 : 度数为奇数的点只能有0或2个
2 存在欧拉回路的充要条件 : 度数为奇数的点只能有0个
二、有向图
1 存在欧拉路径的充要条件 : 要么所有点的出度均=入度；要么除了两个点之外，其余所有点的出度=入度 剩余的两个点:一个满足出度-入度=1(起点) 一个满足入度-出度=1(终点)
2 存在欧拉回路的充要条件 : 所有点的出度均等于入度

铲雪车

随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。
整个城市所有的道路都是双向车道,道路的两个方向均需要铲雪。因为城市预算的削减，整个城市只有 $1$ 辆铲雪车。
铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。
现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？

输入格式
输入数据的第 $1$行表示铲雪车的停放坐标$(x,y)$，$x,y$为整数，单位为米。
下面最多有$4000$行，每行给出了一条街道的起点坐标和终点坐标，坐标均为整数，所有街道都是笔直的，且都是双向车道。
铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转$U$型弯。
铲雪车铲雪时前进速度为 $20$千米/时，不铲雪时前进速度为 $50$千米/时。
保证：铲雪车从起点一定可以到达任何街道。

输出格式
输出铲掉所有街道上的雪并且返回出发点的最短时间，精确到分钟，四舍五入到整数。
输出格式为$\backslash "hours:minutes\backslash "，minutes$不足两位数时需要补前导零。
具体格式参照样例。

数据范围
−106≤x,y≤106−10^6≤x,y≤10^6−106≤x,y≤106

所有位置坐标绝对值不超过 10610^6106。

输入样例：

0 00 0 10000 100005000 -10000 5000 100005000 10000 10000 10000

输出样例：

3:55

样例解释
输出结果表示共需3小时55分钟。

本题每条路是双向道 -> 每条边都要铲两次，所以每个点的出度=入度必然存在欧拉回路。
那么我们的答案就是所有边的长度和$\times 2$（因为两边都要扫雪），然后$÷$速度算出时间。

#include #include #include using namespace std;int main(){ double x1, y1, x2, y2; cin >> x1 >> y1; double sum = 0; while (cin >> x1 >> y1 >> x2 >> y2) { double d1 = x1 - x2; double d2 = y1 - y2; sum += sqrt(d1 * d1 + d2 * d2) * 2; } int minute = round(sum / 1000 / 20 * 60); int hour = minute / 60; minute %= 60; printf(\"%d:%02d\\n\", hour, minute); return 0;}

欧拉路径

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

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

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

接下来$m$行中，第$i$行两个整数vi,uiv_i,u_ivi​,ui​，表示第$i$条边（从$1$开始编号）。
如果$t=1$则表示viv_ivi​到uiu_iui​有一条无向边。如果$t=2$则表示viv_ivi​到uiu_iui​有一条有向边。
图中可能有重边也可能有自环。

点的编号从$1$到$n$。

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

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

如果$t=1$，输出$m$个整数 p1,p2,…,pmp_1,p_2,…,p_mp1​,p2​,…,pm​。令 $e=|pi|$，那么$e$表示经过的第$i$条边的编号。如果$pi$为正数表示从$ve$走到$ue$，否则表示从ueu_eue​走到vev_eve​。如果$t=2$，输出$m$个整数 p1,p2,…,pmp_1,p_2,…,p_mp1​,p2​,…,pm​。其中 pip_ipi​表示经过的第$i$条边的编号。
数据范围
1≤n≤1051≤n≤10^51≤n≤105,0≤m≤2×1050≤m≤2×10^50≤m≤2×105

输入样例1：

13 31 22 31 3

输出样例1：

YES1 2 -3

输入样例2：

25 62 32 53 41 24 25 1

输出样例2：

YES4 1 3 5 2 6

1. 无向图存在欧拉回路：度数必须全是偶数
2. 有向图存在欧拉回路：入度和出度必须相等
3. 有孤立点没关系，只要边全是连通的就行

#include #include using namespace std;const int N = 100010, M = 400010;int h[N], e[M], ne[M], tot;int ans[M], cnt;int din[N], dout[N];bool used[M];int t, n, m;void add(int a, int b){ e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;}void dfs(int u){ for (int &i = h[u]; ~i;) { if (used[i]) { i = ne[i]; continue; } used[i] = 1; if (t == 1) used[i ^ 1] = 1; int edge; if (t == 1) { edge = i / 2 + 1; if (i & 1) edge = -edge; } else edge = i + 1; int j = e[i]; i = ne[i]; dfs(j); ans[cnt ++ ] = edge; }}int main(){ cin >> t >> n >> m; memset(h, -1, sizeof h); for (int i = 1; i <= m; i ++ ) { int a, b; cin >> a >> b; add(a, b); if (t == 1) add(b, a); din[b] ++ , dout[a] ++ ; } if (t == 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]) { dfs(i); break; } } if (cnt < m) { puts(\"NO\"); return 0; } else{ puts(\"YES\"); for (int i = cnt - 1; i >= 0; i -- ) cout << ans[i] << \" \"; } return 0;}

本题是无向图的欧拉路径，如果是欧拉回路（起点和终点同一个），那么任选一点作为起点做dfs求欧拉回路，如果是欧拉路径，选择度数为奇数的点作为起点，做dfs保存欧拉路径。

由于dfs的过程中，存储欧拉路径的数组ans是逆序输出的，因此我们要求逆序字典序最小。
对于每个点经过出边所能到达的所有点，我们按编号从小到大排序，然后访问这样就能得到最小字典序，因为先访问的边后加入到ans数组中，因此当我们逆序输出的时候，就会把编号小的先输出来。

[USACO3.3] 骑马修栅栏 Riding the Fences

John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。

John 的农场上一共有 $m$ 个栅栏，每一个栅栏连接两个顶点，顶点用 $1$ 到 $500$ 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 $1$ 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。

你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 $500$ 进制的数，那么当存在多组解的情况下，输出 $500$ 进制表示法中最小的一个 （也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。

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

输入格式

第一行一个整数 $m$，表示栅栏的数目。

从第二行到第 $(m+1)$ 行，每行两个整数 $u,v$，表示有一条栅栏连接 $u,v$ 两个点。

输出格式

共 $(m+1)$ 行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

数据保证至少有一组可行解。

样例 #1

样例输入 #1

91 22 33 44 24 52 55 65 74 6

样例输出 #1

1234254657

提示
对于 $100\%$ 的数据，$1\le m\le 1024,1\le u,v\le 500$。
题目翻译来自NOCOW。
USACO Training Section 3.3

本题是无向图的欧拉路径，如果是欧拉回路（起点和终点同一个），那么任选一点作为起点做dfs求欧拉回路，如果是欧拉路径，选择度数为奇数的点作为起点，做dfs保存欧拉路径。

由于dfs的过程中，存储欧拉路径的数组ans是逆序输出的，因此我们要求逆序字典序最小。
对于每个点经过出边所能到达的所有点，我们按编号从小到大排序，然后访问这样就能得到最小字典序，因为先访问的边后加入到ans数组中，因此当我们逆序输出的时候，就会把编号小的先输出来。

#include #include using namespace std;const int N = 510, M = 1500;int g[N][N];int ans[M], cnt;int d[N];int n, m;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] += 1, g[b][a] += 1; d[a] ++, d[b] ++ ; n = max(n, a), n = max(n, 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 > 0; i -- ) cout << ans[i] << endl; return 0;}

单词游戏

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

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

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

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

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

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

一个单词可能出现多次。

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

数据范围
1≤N≤1051≤N≤10^51≤N≤105,单词长度均不超过$1000$

输入样例：

32acmibm3acmmalformmouse2okok

输出样例：

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

每个单词看成一条边，首字母和为字母看成图中的顶点。这是一个有向图。
建完图之后，问题就变成了我们能否找到一条路径，依次走过每条边，即该有向图中是否存在欧拉路径？
我们要清楚如何判有向图是否存在欧拉路径，需要满足两个条件：
（1）所有的边要连通；
（2）除了起点和终点外，其余点的入度必须等于出度；
对于（1），可以使用并查集解决，如果某个点有边相连，但是和并查集不连通，说明边不连通。
本题不需要将所有边存储下来，只需要判断连通性以及记录每个点的入度和出度判断是否存在答案即可。

#include #include using namespace std;const int N = 30, M = 100010;int din[N], dout[N];int fa[N];bool st[N];char str[1010];int t, n;int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]);}int main(){ cin >> t; while (t -- ) { memset(st, 0, sizeof st); memset(din, 0, sizeof din); memset(dout, 0, sizeof dout); cin >> n; for (int i = 0; i < 26; i ++ ) fa[i] = i; for (int i = 1; i <= n; i ++ ) { scanf(\"%s\", str); int len = strlen(str); int a = str[0] - \'a\', b = str[len - 1] - \'a\'; din[b] ++, dout[a] ++ ; st[a] = st[b] = 1; fa[find(a)] = find(b); } bool success = 1; int start = 0, end = 0; for (int i = 0; i < 26; i ++ ) { if (dout[i] != din[i]) { if (dout[i] - din[i] == 1) start ++ ; else if (din[i] - dout[i] == 1) end ++ ; else{  success = 0;  break; } } } if (success == 1 && !((start == 0 && end == 0) || (start == 1 && end == 1))) success = 0; int root = -1; for (int i = 0; i < 26; i ++ ) { if (st[i]) { if (root == -1) root = find(i); else if (root != find(i)) {  success = 0;  break; } } } if (success) puts(\"Ordering is possible.\"); else puts(\"The door cannot be opened.\"); } return 0;}

艺术字体转换器