主要考英语或者数学基础。
一幅连通图的奇点个数为0或2时才能够被一笔画。
连通图的判断用DFS来计数。
连通图+0个奇点:Eulerian
连通图+2个奇点:semi-Eulerian
非连通图/连通图+其他数量的奇点:non-Eulerian
AC代码
#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>using namespace std;const int SUP = 100000000;
const int maxn = 510;int degree[maxn] = {0};int vNum,eNum;vector<int> G[maxn];int cnt = 0;
bool vis[maxn] = {0};void DFS(int root){vis[root] = 1;cnt ++;for(int i=0;i<G[root].size();i++){int j = G[root][i];if(vis[j]==0)DFS(j);}
}int main(){cin>>vNum>>eNum;for(int i=0;i<eNum;i++){int v1,v2;cin>>v1>>v2;degree[v1]++;degree[v2]++;G[v1].push_back(v2);G[v2].push_back(v1);}int oddN = 0;for(int i=1;i<=vNum;i++){if(degree[i]%2!=0){oddN ++;}printf("%d%s",degree[i],i==vNum?"\n":" ");}DFS(1);if(oddN==0&&cnt==vNum)printf("Eulerian\n");else if(oddN==2&&cnt==vNum)printf("Semi-Eulerian\n");else printf("Non-Eulerian");return 0;
}