lng企业自建站,我做钓鱼网站自首了,河南第二建设集团网站视频,乐陵建设网站文章目录 定义欧拉路径的性质#xff1a;1123. 铲雪车边编号输出欧拉路径#xff1a;1184. 欧拉回路点编号字典序最小输出欧拉路径#xff1a;1124. 骑马修栅栏并查集判断有向图是否存在欧拉路径#xff1a;1185. 单词游戏 定义 小学一笔画问题#xff0c;每条边只经过一次… 文章目录 定义欧拉路径的性质1123. 铲雪车边编号输出欧拉路径1184. 欧拉回路点编号字典序最小输出欧拉路径1124. 骑马修栅栏并查集判断有向图是否存在欧拉路径1185. 单词游戏 定义 小学一笔画问题每条边只经过一次 判断图是否存在欧拉回路判断图是否连通存在孤立边再根据有向/无向具体判断
对于无向图来说欧拉路径中起点和终点的度数为奇数中间点的度数为偶数 起点和终点开始和结束时必须经过一条边其余情况为从一条边进入再从另一条边离开即度数为1 2 * n 中间点一条边进入一条边离开度数为2 * n
欧拉回路中所有点的度数为偶数
七桥问题中由于每个点的度数为奇数所以不可能存在欧拉路径 以下结论直接记 欧拉路径的性质1123. 铲雪车
1123. 铲雪车 - AcWing题库
根据题意所有的街道都是双向说明这张图是一张有向图。每个城市都连接了街道说明这张图是连通图。将每个城市看成点那么每个点的入度都等于出度这张图存在欧拉回路所以无论如何我们都有一条路径能够不重复不遗漏的遍历所有的边而这道题要求时间最短路径我们不需要算出具体的欧拉回路以为欧拉回路的距离一定是所有路径之和只要根据题意将路径转换成时间即可
#include iostream
#include cmath
using namespace std;int main()
{double x1, y1, x2, y2;scanf(%lf%lf, x1, y1);double sum 0;while (~scanf(%lf%lf%lf%lf, x1, y1, x2, y2)){double x x1 - x2, y y1 - y2;sum sqrt(x * x y * y) * 2;}int mte round(sum / 1000 * 60 / 20);int hour mte / 60;mte % 60;printf(%d:%02d\n, hour, mte);return 0;
}debug距离要乘2每条道路都是双向的 边编号输出欧拉路径1184. 欧拉回路
1184. 欧拉回路 - AcWing题库
欧拉路径的板子 若一张图存在欧拉路径可以用dfs递归完所有的边在dfs回溯时记录边的编号到数组中最后逆着输出该数组即可 用uesd数组标记已经遍历过的边同时每遍历完一条边就删除这条边防止重复遍历 其实有向图不需要使用used数组只要删除遍历完的边即可 开uesd数组是因为无向图由于我们用单链表存储边虽然可以删除当前正在遍历的边但是在无向图中删除反向边比较麻烦所以这里用uesd数组标记反向边保证每条边只会遍历一次
需要注意不要遍历孤立点若图中存在欧拉路径孤立点不会影响欧拉路径 还要注意这题的无向图的欧拉回路中若边的方向与输入给定的方向不同那么需要输出编号的负数
#include iostream
#include cstring
using namespace std;const int N 1e5 10, M 4e5 10;
int h[N], e[M], ne[M], idx;
int din[N], dout[N];
int ans[M / 2], cnt;
bool used[M];
int type, n, m;void add(int x, int y)
{e[idx] y, ne[idx] h[x], h[x] idx ;
}void dfs(int x)
{for (int i h[x]; i ! -1;){if (used[i]){i ne[i];continue;}int t; // 当前边的编号used[i] true;if (type 1) {used[i ^ 1] true;t i / 2 1;if (i 1) t -t;}else t i 1;int y e[i];i ne[i];dfs(y);ans[ cnt] t;}
}int main()
{memset(h, -1, sizeof(h));cin type n m;int x, y;for (int i 0; i m; i ){scanf(%d%d, x, y);add(x, y);if (type 1) add(y, x);din[y] , dout[x] ;}if (type 1)for (int i 1; i n; i )if ((din[i] dout[i]) % 2){puts(NO);return 0;}if (type 2)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 m; i ; -- i )printf(%d , ans[i]);puts();return 0;
}要特别注意求欧拉路径后必须要判断这条路径是否遍历了所有的边 点编号字典序最小输出欧拉路径1124. 骑马修栅栏
1124. 骑马修栅栏 - AcWing题库
题目要求按照点的编号最小字典序输出欧拉路径可以dfs(x)时可以先遍历与x相连的编号较小的点那么与x相连的点中相较于编号较大的点编号较小的点将被存储到序列的靠后位置逆序后编号较小的点位于序列的靠前位置满足最小字典序
为什么不使用邻接表存储图 用邻接表存储图时选择编号较小的点会比较麻烦需要对单链表中的元素进行排序 用邻接矩阵存储图直接按照下标从小到大dfs与x相连的点即可
需要注意的是题目可能存在重边通常邻接矩阵存储边权的最小/大值但是这题需要存储两点间边的数量以保证之后的dfs中每条边都被遍历 还有一点图是无向图但题目没有说存在欧拉回路还是欧拉路径如果存在欧拉路径那么起点和终点的度数为奇数。如果存在欧拉回路那么所有点的度数为偶数 所以dfs之前需要找度数为奇数的点若找到说明该图一定存在欧拉路径可能不存在欧拉回路。此时从度数为偶数的点dfs将无法正确遍历欧拉路径只有存在欧拉回路的情况下才能从度数为偶数的点dfs 并且1不是最小的点编号点编号范围在1~500所以要找到一个度数非0的点编号再找是否存在欧拉路径最后再dfs 由于使用邻接矩阵存储无向图所以不需要开used数组每次遍历一条边能够很简单地删除这条边和其反向边
#include iostream
using namespace std;const int N 510, M 2100;
int g[N][N], d[N];
int ans[M], cnt;
int n, m;void dfs(int x)
{for (int y 1; y N; y ){if (g[x][y]){g[x][y] -- , g[y][x] --;dfs(y);}}ans[ cnt ] x;
}int main()
{scanf(%d, m);int x, y;for (int i 0; i m; i ){scanf(%d%d, x, y);g[x][y] , g[y][x] ;d[x] , d[y] ;}int start 1;while (!d[start]) start ;for (int i start; 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;
}并查集判断有向图是否存在欧拉路径1185. 单词游戏
1185. 单词游戏 - AcWing题库
建图方式以单词的第一个字母或最后一个字母为点从前往后建一条有向边 问题转换成判断有向图中是否存在欧拉路径当然可能也是欧拉回路 由于不需要找出具体的欧拉路径所以可以不用dfs只要满足所有点的入度等于出度欧拉回路或者欧拉路径入度比出度多1终点出度比入度多1起点 该图就存在欧拉路径当然还需要判断是否有孤立边由于这题特殊的建图方式若存在一个单词是孤立的那么在图中表现为两点一边的孤立 判断是否存在孤立边可以dfs跑一遍欧拉路径判断边数是否小于图的边数 但是可以用更简单的并查集维护每个点属于的集合建完图后一旦出现两点属于不同集合那么图中一定存在孤立边因为该图中的点一定连接着一条边所以点孤立边孤立
#include iostream
#include cstring
using namespace std;const int N 30, M 1e5 10;
bool st[N];
int din[N], dout[N];
int p[N];
int T, m;int find(int x)
{if (x ! p[x]) p[x] find(p[x]);return p[x];
}int main()
{scanf(%d, T);while (T -- ){memset(st, false, sizeof(st));memset(din, 0, sizeof(din));memset(dout, 0, sizeof(dout));for (int i 0; i 26; i ) p[i] i;char str[1010];scanf(%d, m);for (int i 0; i m; i ){scanf(%s, str);int len strlen(str);int x str[0] - a, y str[len - 1] - a;st[x] st[y] true;din[y] , dout[x] ;p[find(x)] p[find(y)];}int start 0, end 0; // 起点和终点的数量bool flag true;for (int i 0; i 26; i )if (din[i] ! dout[i]){if (din[i] 1 dout[i]) end ;else if (din[i] dout[i] 1) start ;else {flag false;break;}}if (flag !((!start !end) || (start 1 end 1))) // 起点数和终点数不正确flag false;// 判断是否存在孤立边int t -1;for (int i 0; i 26; i )if (st[i]){if (t -1) t find(i);else if (t ! find(i)){flag false;break;}}if (flag) puts(Ordering is possible.);else puts(The door cannot be opened.);}return 0;
}
