题目链接:点击打开链接
题目大意:如果一个连通图的所有结点的度都是偶数,那么它就是Eulerian,如果除了两个结点的度是奇数其他都是偶数,那么它就是Semi-Eulerian,否则就是Non-Eulerian。
解题思路:用邻接表存储图,判断每个结点的度【即:每个结点i的v[i].size()】是多少即可得到最终结果~注意:图必须是连通图,所以要用一个深搜判断一下连通性,从结点1开始深搜,如果最后发现统计的连通结点个数cnt != n说明是不是连通图,要输出Non-Eulerian。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=520; int n,m,cnt; int vis[maxn]; vector<int> vec[maxn]; void dfs(int id) { vis[id]=1; cnt++; for(int i=0;i<vec[id].size();i++) if(!vis[vec[id][i]]) dfs(vec[id][i]); } int main() { int u,v,even=0; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); } dfs(1); for(int i=1;i<=n;i++) if(vec[i].size()%2==0) even++; for(int i=1;i<=n;i++) printf("%d%c",vec[i].size(),i==n?'\n':' '); if(cnt==n && even==n) puts("Eulerian"); else if(cnt==n && even+2==n) puts("Semi-Eulerian"); else puts("Non-Eulerian"); return 0; }