安徽餐饮加盟网站建设,上海正规做网站公司有哪些,wordpress网站音乐播放,网站模板 wordpress描述 zyc从小就比较喜欢玩一些小游戏#xff0c;其中就包括画一笔画#xff0c;他想请你帮他写一个程序#xff0c;判断一个图是否能够用一笔画下来。 规定#xff0c;所有的边都只能画一次#xff0c;不能重复画。 输入第一行只有一个正整数N(N10)表示测试数据的组数…描述 zyc从小就比较喜欢玩一些小游戏其中就包括画一笔画他想请你帮他写一个程序判断一个图是否能够用一笔画下来。 规定所有的边都只能画一次不能重复画。 输入第一行只有一个正整数N(N10)表示测试数据的组数。每组测试数据的第一行有两个正整数P,Q(P1000,Q2000)分别表示这个画中有多少个顶点和多少条连线。点的编号从1到P随后的Q行每行有两个正整数A,B(0A,BP)表示编号为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 可以用并查集做也可以直接建图做。 因为正在加班加点的学习数据结构于是先建图做了一次。 参考了http://www.cnblogs.com/dongsheng/archive/2012/06/04/2534489.html 建图 //Asimple#include stdio.h
#include iostream
#include algorithmusing namespace std;const int maxn 1005;
int n, T, num, cnt, point, line, x, y;
int G[maxn][maxn];
int vis[maxn];//标记数组标记是否走过
int p[maxn];//每个节点的度//图的DFS
//欧拉图节点度数全部为偶数
//半欧拉图有且只有两个度数为奇数的节点
//这两种图都可以一笔画出。void DFS(int i)
{int v;vis[i] 1 ;for(v0; vpoint; v)if( v!i G[i][v] !vis[v])DFS(v);
}int main()
{cin T ;while( T -- ){cnt 0 ;bool flag true ;cin point line ;memset(p,0,sizeof(p));memset(vis,0,sizeof(vis));memset(G,0,sizeof(G));for(int i0; iline; i){cin x y ;G[x-1][y-1] G[y-1][x-1] 1 ;//建图 p[x-1] ; p[y-1] ;//统计 各节点的度}DFS(0);//判断是否连通for(int i0; ipoint; i){G[i][i] 1 ;if( vis[i]0 ) flag false ;if( p[i]1 ) cnt ;}if( flag )//是连通图{if( cnt0 || cnt2 ) cout Yes endl ;else cout No endl ;}else cout No endl ;}return 0;
}并查集 #include cstdio
#include iostream
#include cstringusing namespace std;int father[1005], deg[1005];int find(int k)
{if(k father[k])return k;elsereturn father[k] find(father[k]);
}int main()
{int T, p, q, a, b;scanf(%d, T);while(T--){scanf(%d%d, p, q);for(int i 1; i p; i){father[i] i;deg[i] 0;}while(q--){scanf(%d%d, a, b);deg[a];deg[b];int fa find(a);int fb find(b);if(fa ! fb)father[fa] fb;}int cnt1, cnt2;cnt1 cnt2 0;for(int i 1; i p; i){if(father[i] i){cnt1;if(cnt1 1)break;}if(deg[i] 1)cnt2;}if(cnt1 1)printf(No\n);else{if(cnt2 0 || cnt2 2)printf(Yes\n);elseprintf(No\n);}}return 0;
}转载于:https://www.cnblogs.com/Asimple/p/5532803.html
