描述
判断一个图是否能够用一笔画下来.规定,所有的边都只能画一次,不能重复画。
输入
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000),分别表示这个画中有多少个顶点和多少条连线。(点的编号从1到P)
随后的Q行,每行有两个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。
输出
如果存在符合条件的连线,则输出"Yes",
如果不存在符合条件的连线,输出"No"。
样例输入
2
43
12
13
14
45
12
23
13
14
34
样例输出
No
Yes
思路:
1.先判断图是否为连通图,不连通则一笔无法画出。
2.若为连通图,根据欧拉回路判断即可。
1、基本概念:
(1)定义
欧拉通路(欧拉迹)—通过图中每条边一次且仅一次,并且过每一顶点的通路。
欧拉回路(欧拉闭迹)—通过图中每条边一次且仅一次,并且过每一顶点的回路。
欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点的那种图,即不重复的行遍所有的边再回到出发点。
通路和回路-称vie1e2…envj为一条从vi到vj且长度为n的通路,其中长度是指通路中边的条数.称起点和终点相同的通路为一条回路。
简单图-不含平行边和自回路的图。
混合图-既有有向边,也有无向边的图
平凡图-仅有一个结点的图
完全图-有n个结点的且每对结点都有边相连的无向简单图,称为无向完全图;有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。
(2)欧拉图的特征:
无向图
a)G有欧拉通路的充分必要条件为:G连通,G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
b)G有欧拉回路(G为欧拉图):G连通,G中均为偶度顶点。
有向图
a)D有欧拉通路:D连通,除两个顶点外,其余顶点的入度均等于出度,这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1。
b)D有欧拉回路(D为欧拉图):D连通,D中所有顶点的入度等于出度。一个有向图是欧拉图,当且仅当该图所有顶点度数都是0。
代码如下:
其中unionsearch可以使用递归得出
另一种思路:
分享到:
相关推荐
二年级奥数.几何.一笔画问题.docx
NULL 博文链接:https://dlzjp123.iteye.com/blog/481358
四年级奥数第一讲一笔画问题.doc
信息学竞赛系列教程,欧拉回路和欧拉路径的基本性质,一笔画问题的两种不同解法。
判断一个图是否能够用一笔画下来。 规定,所有的边都只能画一次,不能重复画。 输入 第一行只有一个正整数N(N)表示测试数据的组数。 每组测试数据的第一行有两个正整数P,Q(P,Q),分别表示这个画中有多少个顶点...
一笔画问题——七桥问题的解决.docx
欧拉通路回路和一笔画问题1
二年级奥林匹克数学 一笔画问题习题 试题.doc
二年级奥数.几何.一笔画问题.doc
java 编写的小游戏 适合初学者学习
对于给定的N个点和连接这些点的M条边,编程计算一笔画回路
Python语言实现了用傅里叶级数展开指定图像的一笔画。
算法设计经典问题集 【题目1】N皇后问题(八皇后问题的扩展) 【题目2】排球队员站位问题 ...【题目16】一笔画问题 【题目17】城市遍历问题 【题目18】棋子移动问题 【题目19】求集合元素问题(1,2x+1,3X+1类)
一笔画HTML5游戏源码,运行需要服务器环境,已经反复测试,放心使用。
【题目1】N皇后问题(八皇后问题的扩展) 【题目2】排球队员站位问题 【题目3】把自然数N分解为若干...【题目16】一笔画问题 【题目17】城市遍历问题. 【题目18】棋子移动问题 【题目19】求集合元素问题(1,2x+1,3X+1类)
【题目1】N皇后问题(八皇后问题的扩展) 【题目2】排球队员站位问题 【题目3】把自然数N分解为若干...【题目16】一笔画问题 【题目17】城市遍历问题. 【题目18】棋子移动问题 【题目19】求集合元素问题(1,2x+1,3X+1类)
微信一笔画完辅助的代码,自动执行的批处理文件 仅仅用来学习交流,有问题可以看对应的步骤解析
【题目1】N皇后问题(八皇后问题的扩展) 【题目...求迷宫的路径.(深度优先搜索法) 【题目16】一笔画问题 【题目17】城市遍历问题. 【题目18】棋子移动问题 【题目19】求集合元素问题(1,2x+1,3X+1类)