题目链接
一笔画成问题类“七桥问题”每条边走一次，这题是可以回到原点也可以不回到原点。首先要确定是一个无向图，因为一笔画成没有规定一一定要从哪个点或者边开始。
关于欧拉图的理解可以参考下：知识点
对了，首先要先判断这个图的连通性！继而才有可能是欧拉图~
我用的深搜判断图的连通性，可以用并查集
#include<stdio.h> #include<vector> #include<string.h> using namespace std; int vis[1005]; int degree[1005]; int n,m,count; vector<int>e[2005]; int dfs(int u) { int i,v; for(i=0;i<e[u].size();i++) { v=e[u][i]; if(!vis[v]) { vis[v]=1; dfs(v); count++; } } } int main() { int T; scanf("%d",&T); while(T--) { int i,u,v; int num; memset(degree,0,sizeof(degree)); scanf("%d%d",&n,&m); for(i=0;i<=n;i++) { e[i].clear(); } while(m--) { scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); degree[u]++; degree[v]++; } memset(vis,0,sizeof(vis)); vis[1]=1; count=1; dfs(1); num=0; if(count==n) { for(i=1;i<=n;i++) { if(degree[i]%2!=0) num++; } if(num==0||num==2)//度数为奇数的个数为0个或2个时可以满足一笔画成 printf("Yes\n"); else printf("No\n"); } else printf("No\n"); } return 0; }
