一笔画问题
时间限制：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"。 - 样例输入
-
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。当然首先该图是连通图，而且 算法的优劣性就体现在判断图是否为连通图上。
一般判断连通图，用DFS。首先贴上用DFS解决的又臭又长的代码。
01.#include
<iostream>02.#include
<memory.h>03.using namespace std;04. 05.const int maxp=1005;06. 07.int deg[maxp],connect[maxp][maxp],vis[maxp];08.int P,Q;09. 10.void dfs(int k)11.{12.vis[k]=1;13.for(int i=1;i<=P;i++)14.{15.if(connect[k][i]&&vis[i]==0)16.{17.dfs(i);18.}19.}20.}21. 22.int main()23.{24.int N,A,B;25.cin>>N;26.while(N--)27.{28.cin>>P>>Q;29.int flag=true,count=0;30.memset(deg,0,sizeof(deg));31.memset(connect,0,sizeof(connect));32.memset(vis,0,sizeof(vis));33.for(int i=0;i<Q;i++)34.{35.cin>>A>>B;36.connect[A][B]=connect[B][A]=1;37.deg[A]++;38.deg[B]++;39.}40.for(int i=1;i<=P;i++)41.{42.if(deg[i]==0)43.{44.flag=false;45.break;46.}47.if(deg[i]%2!=0)48.count++;49.}50.if(count!=0&&count!=2)flag=false;51.if(flag)52.{53.dfs(1);54.for(int i=1;i<=P;i++)55.{56.if(vis[i]==0)57.{58.flag=false;59.break;60.}61.}62.}63.cout<<(flag?"Yes":"No")<<endl;64.}65.return 0;66.}
然后看一段简练的代码，有比较才有好坏嘛。这是NYOJ上排名第一的算法。
度的判断一样，主要区别是判断是否连通。运用并查集的方法。读入一个边，判断这两个点是否在一个集合里，不在的话就加入一个集合，并计数一次。如果一张图是连通的，一般会计数n-1次（n是顶数），如果是不连通的，计数会小于n-1。代码22行到25行就是该过程。
#include<stdio.h>02.#include<string.h>03.int father[1002];04.int Find(int x)05.{06.if(father[x]==-1) return x;07.return father[x]=Find(father[x]);08.}09.int main()10.{11.int n,m,T,i,in[1002],a,b,sum,f;12.scanf("%d",&T);13.while(T--)14.{15.memset(in,0,sizeof(in));16.memset(father,-1,sizeof(father));17.scanf("%d%d",&n,&m);18.for(i=0,sum=0;i<m;i++)19.{20.scanf("%d%d",&a,&b);21.++in[a];
++in[b];22.a=Find(a);
b=Find(b);23.if(a!=b)
{ father[a]=b; sum++; }24.}25.if(sum<n-1)
{ printf("No\n"); continue;
}26.for(i=1,f=0;i<=n;i++)27.if(in[i]%2)
{ f++; if(f>2) break;
}28.if(f==0||f==2) printf("Yes\n");29.else printf("No\n");30.}31.}