zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。
?
规定，所有的边都只能画一次，不能重复画。
?
?
?
?
输入
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到P）
随后的Q行，每行有两个正整数A,B(0
28 ? ? ? ??
输出
如果存在符合条件的连线，则输出"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
本题来自：http://acm.nyist.net/JudgeOnline/problem.php?pid=42
?
问题分析：
?
欧拉定理 ? 如果一个网络是连通的并且奇顶点的个数等于0或2，那么它可以一笔画出；否则它不可以一笔画出。
?
判断一笔画的方法：
?
①是连通的。一个图，如果图上任意二点总有线段连接着，就称为连通的。不是连通的就不能一笔画出。
?
②奇点个数是0或者是2。图上线段的端点可以分成二类，奇点和偶数。一个点，以它为端点的线段数是奇数就称为奇点，线段数是偶数就称为偶点。
?
一个图是否是一笔画就看奇点的个数，奇点个数是 0 或者 2，就是一笔画，否则就不是一笔画。
?
所以这个问题完全可以转化策略为：
?
? ? ? ? ? ?第一步： 首先我们不管它三七二十几，先进行连通性的判断。
?
? ? ? ? ? ?第二步：
?
? ? ? ? ? ? ? ? ? ? ? （1）如果是连通的，我们来判断此图的度的奇点的个数是0或者是2 ，如果是，则说明这个是欧拉图，即可以一笔画出，反之则不能一笔画出
?
? ? ? ? ? ? ? ? ? ? ? （2）如果是非连通的，这说明这个图很定不能一笔画出。
?
?
?
代码一：——深搜
?
?
?
复制代码
?1 #include
?2 #include
?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));
29 ? ? ? ? scanf("%d%d",&P,&Q);
30?
31 ? ? ? ? for(int i=0;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 ? ? ? ? else
49 ? ? ? ? {
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
?3 #include
?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 ? ? ?else
15 ? ? ? ? ? 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 ? ? ? ? ? e