首页 > 代码库 > NYOJ 42 一笔画问题
NYOJ 42 一笔画问题
一笔画问题
时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。
规定，所有的边都只能画一次，不能重复画。
- 输入
- 第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到P）
随后的Q行，每行有两个正整数A,B(0<A,B<P)，表示编号为A和B的两点之间有连线。 - 输出
- 如果存在符合条件的连线，则输出"Yes",
如果不存在符合条件的连线，输出"No"。 - 样例输入
24 31 21 31 44 51 22 31 31 43 4
- 样例输出
NoYes
本题来自：http://acm.nyist.net/JudgeOnline/problem.php?pid=42
问题分析：
欧拉定理 如果一个网络是连通的并且奇顶点的个数等于0或2，那么它可以一笔画出；否则它不可以一笔画出。
判断一笔画的方法：
①是连通的。一个图，如果图上任意二点总有线段连接着，就称为连通的。不是连通的就不能一笔画出。
②奇点个数是0或者是2。图上线段的端点可以分成二类，奇点和偶数。一个点，以它为端点的线段数是奇数就称为奇点，线段数是偶数就称为偶点。
一个图是否是一笔画就看奇点的个数，奇点个数是 0 或者 2，就是一笔画，否则就不是一笔画。
所以这个问题完全可以转化策略为：
第一步： 首先我们不管它三七二十几，先进行连通性的判断。
第二步：
（1）如果是连通的，我们来判断此图的度的奇点的个数是0或者是2 ，如果是，则说明这个是欧拉图，即可以一笔画出，反之则不能一笔画出
（2）如果是非连通的，这说明这个图很定不能一笔画出。
代码一：——深搜
1 #include <stdio.h> 2 #include <string.h> 3 int P,Q; 4 int bian[1005]; 5 bool map[1005][1005],vis[1005]; 6 void dfs(int cur) 7 { 8 vis[cur]=true; 9 for(int i=1;i<=P;i++)10 if(map[cur][i])11 {12 bian[cur]++;13 if(!vis[i])14 dfs(i);15 }16 }17 18 int main()19 {20 int T;21 scanf("%d",&T);22 while(T--)23 {24 int ok=1;25 memset(map,false,sizeof(map));26 memset(vis,false,sizeof(vis));27 memset(bian,0,sizeof(bian));28 29 scanf("%d%d",&P,&Q);30 31 for(int i=0;i<Q;i++)32 {33 int A,B;34 scanf("%d%d",&A,&B);35 map[A][B]=true,map[B][A]=true;36 }37 38 dfs(1); // 判断是否连通的，如果vis有个false，就不是连通的39 40 for(int i=1;i<=P;i++)41 if(!vis[i])42 {43 ok=0;44 break;45 }46 47 if(!ok)printf("No\n");48 else49 {50 int xx=0;51 for(int i=1;i<=P;i++)52 if(bian[i]%2)xx++;53 if(xx==0||xx==2)printf("Yes\n");54 else printf("No\n");55 }56 }57 return 0;58 }
在AC后，网上看到别人的思路，还有一种方法来判断连通性——并查集。
并查集资料：http://www.cnblogs.com/cyjb/p/UnionFindSets.html
代码二：——并查集
1 //并查 2 #include<stdio.h> 3 #include<string.h> 4 int father[1010],ans[1010]; 5 void init() 6 { 7 for(int i=0;i<1010;i++) 8 father[i]=i; 9 }10 int find(int x)11 {12 if(father[x]==x)13 return x;14 else15 return father[x]=find(father[x]);16 }17 int main()18 {19 int ncases,n,m,x,y,count,jdcount;20 scanf("%d",&ncases);21 while(ncases--)22 {23 memset(ans,0,sizeof(ans));24 init();25 count=jdcount=0;26 scanf("%d %d",&n,&m);27 for(int i=1;i<=m;i++)28 {29 scanf("%d %d",&x,&y);30 ans[x]++; ans[y]++;31 x=find(x); y=find(y);32 if(x!=y)33 father[x]=father[y];34 }35 36 for(i=1;i<=n;i++)37 if(find(i)==i)38 count++;39 for(i=1;i<=n;i++)40 if(ans[i]%2==1)41 jdcount++;42 if((jdcount==0||jdcount==2)&&count==1)43 printf("Yes\n");44 else45 printf("No\n");46 }47 }
NYOJ 42 一笔画问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。