1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=1005; 5 int T,n,m,deg[maxn],fa[maxn],a,b,f1,f2; 6 void init(){ 7 for(int i=1;i<=n;++i)fa[i]=i; 8 } 9 int findt(int x){ 10 int per=x,tmp; 11 while(fa[per]!=per)per=fa[per]; 12 while(x!=per){tmp=fa[x];fa[x]=per;x=tmp;} 13 return x; 14 } 15 void unite(int x,int y){ 16 x=findt(x),y=findt(y); 17 if(x!=y)fa[x]=y; 18 } 19 int main(){ 20 while(cin>>n&&n){ 21 cin>>m; 22 memset(deg,0,sizeof(deg));init();f1=f2=0; 23 while(m--){ 24 cin>>a>>b; 25 deg[a]++,deg[b]++; 26 unite(a,b); 27 } 28 for(int i=1;i<=n;++i) 29 f1+=(i==fa[i]?1:0),f2+=(deg[i]&1?0:1); 30 if(f1==1&&f2==n)puts("1");///欧拉回路 31 else puts("0"); 32 33 } 34 return 0; 35 }
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
解题思路：
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=1005; 5 int T,n,m,deg[maxn],fa[maxn],a,b,f1,f2; 6 void init(){ 7 for(int i=1;i<=n;++i)fa[i]=i; 8 } 9 int findt(int x){ 10 int per=x,tmp; 11 while(fa[per]!=per)per=fa[per]; 12 while(x!=per){tmp=fa[x];fa[x]=per;x=tmp;} 13 return x; 14 } 15 void unite(int x,int y){ 16 x=findt(x),y=findt(y); 17 if(x!=y)fa[x]=y; 18 } 19 int main(){ 20 while(cin>>n>>m){ 21 memset(deg,0,sizeof(deg));init();f1=f2=0;///f1判断是否是连通图，f2统计每个节点的度 22 while(m--){ 23 cin>>a>>b; 24 deg[a]++,deg[b]++; 25 unite(a,b); 26 } 27 for(int i=1;i<=n;++i) 28 f1+=(i==fa[i]?1:0),f2+=(deg[i]&1?0:1); 29 if(f1==1&&(f2==n||n-f2==2))puts("Yes");///如果每个节点的度都是偶数，或者有两个奇数度的节点，就能一笔画出 30 else puts("No"); 31 32 } 33 return 0; 34 }
原文：https://www.cnblogs.com/acgoto/p/10046938.html