一笔画问题
时间限制:3000 ms | 内存限制:65535 KB
难度:4
zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。
规定,所有的边都只能画一次,不能重复画。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000),分别表示这个画中有多少个顶点和多少条连线。(点的编号从1到P)
随后的Q行,每行有两个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。
如果不存在符合条件的连线,输出"No"。
2 4 3 1 2 1 3 1 4 4 5 1 2 2 3 1 3 1 4 3 4
No Yes
思路:
满足欧拉回路或者通路性质即可,这连通图基础上,存在 0 个或者 2 个奇数度结点即可。所以还要判断是不是连通图,用并查集。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int v, e; int root[1005], ans[1005]; void init () { for (int i = 1; i <= v; ++i) { root[i] = i; ans[i] = 0; } } int Find (int x) { return x == root[x] ? x : root[x] = Find(root[x]); } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &v, &e); init(); while (e--) { int a, b, A, B; scanf("%d%d", &a, &b); ++ans[a]; ++ans[b]; A = Find(a); B = Find(b); root[A] = B; } int num = 0; for (int i = 1; i <= v; ++i) { if (root[i] == i) ++num; } if (num > 1) printf("No\n"); else { num = 0; for (int i = 1; i <= v; ++i) { if (ans[i] % 2) ++num; } if (num == 2 || !num) printf("Yes\n"); else printf("No\n"); } } return 0; }
相关推荐
信息学竞赛系列教程,欧拉回路和欧拉路径的基本性质,一笔画问题的两种不同解法。
欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结,...
这是一款基于QT实现的一笔画软件,该项目的背景起源于中国邮递员问题,本程序用来模拟邮递员选择最短路径送完所有快递再回到出发点。具体来说,用户可以通过的工具栏在画板区域进行画点并连线,最后形成的图如果能够...
【摘要】欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关
欧拉通路回路和一笔画问题1
【摘要】欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关
NULL 博文链接:https://dlzjp123.iteye.com/blog/481358
图的应用之一:一笔画问题 编程找出图的一笔画路线
二年级奥数.几何.一笔画问题.docx
四年级奥数第一讲一笔画问题.doc
对于给定的N个点和连接这些点的M条边,编程计算一笔画回路
判断一个图是否能够用一笔画下来。 规定,所有的边都只能画一次,不能重复画。 输入 第一行只有一个正整数N(N)表示测试数据的组数。 每组测试数据的第一行有两个正整数P,Q(P,Q),分别表示这个画中有多少个顶点...
java 编写的小游戏 适合初学者学习
一笔画问题——七桥问题的解决.docx
二年级奥林匹克数学 一笔画问题习题 试题.doc
二年级奥数.几何.一笔画问题.doc
一笔画HTML5游戏源码,运行需要服务器环境,已经反复测试,放心使用。
微信一笔画完辅助的代码,自动执行的批处理文件 仅仅用来学习交流,有问题可以看对应的步骤解析
一个一笔画游戏,可以自定义关卡,蓝线走一次,橙色路线走两次,粉红色路线走三次