描述
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
通过图(有向图,无向图)中所有边且每边仅通过一次通路称为欧拉通路，相应的回路称为欧拉回路。
一笔画中两点之间的连线为一条边。所有边只能画一遍，典型的欧拉回路的题目。
思路：
1.建立邻接矩阵用来记录边。
2.判断由该邻接矩阵构成的图是否能形成欧拉回路。
/**
*欧拉回路存在的条件：
*1.判断是否连通(连通)
*2.判断度数为奇数的结点个数(2个或者0个)
*/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define N 1005
using namespace std;
int t,a,b;
int x,y;
int G[N][N];//邻接矩阵
int vis[N];//访问标识
int p[N];//统计各个结点的度
//求从u出发的连通块
void dfs(int u){vis[u]=1;for(int v=1 ;v<=a ;v++){if(!vis[v]&&G[u][v]){vis[v]=1;dfs(v);}}
}int main(){scanf("%d",&t);while(t--){scanf("%d%d",&a,&b);memset(p,0,sizeof(p));memset(vis,0,sizeof(vis));memset(G,0,sizeof(G));for(int i=0 ;i<b ;i++){scanf("%d%d",&x,&y);G[x][y]=1;G[y][x]=1;G[i][i]=1;p[x]++;p[y]++;}//判断是否连通 dfs(1);int flag = 1;int count = 0;for(int i=1 ;i<=a ;i++){if(vis[i]==0){//有未标识的结点(不连通) flag = 0;}if(p[i]%2){//度是奇数的结点的个数 ++count;}}if(flag){ if(count==2||count==0){//都是偶数或者有2个是奇数 puts("Yes");}else{puts("No");}}else{puts("No");}} return 0;
}