前言

传送门

正文在这里插入图片描述


参考题解

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;

/* 题意： 给定一个无向图，要你判断这个图是一个欧拉图还是半欧拉图，还是非欧拉图 思路： 首先什么是欧拉图？根据题意可得如下要求 1、 连通图所有的结点的度都是偶数 2、 如果奇数度的点有且仅有两个，那么它是半欧拉图 3、 既不是欧拉图也不是半欧拉图的为非欧拉图 4、非连通图一定不是欧拉图 */
const int N=5e2+10; 
int n,m;	
int oddCnt=0,evenCnt=0;//oddCnt表示度数奇数的结点个数，evenCnt则表示度数为偶数的结点个数 
bool vis[N];
vector<int> g[N];
int degree[N];//degree[i]表示结点i的度数 
void dfs(int index){
	if(vis[index])return;
	vis[index]=true;
	degree[index]=g[index].size();
	if(degree[index]%2==0)evenCnt++;
	else oddCnt++; 
	for(int i=0;i<g[index].size();i++){
		if(!vis[g[index][i]]){
			dfs(g[index][i]);
		}
	} 
}
int main(){
	fill(vis,vis+N,false);
	cin>>n>>m;	
	for(int i=0,a,b;i<m;i++){
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int cnt=0;//连通分量的个数 
	// 遍历判断是否是连通图 
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			cnt++;
		}
	}
	//输出每个结点的度数
	for(int i=1;i<=n;i++){
		if(i!=1)printf(" ");
		printf("%d",degree[i]);
	} 
	cout<<endl;
	//根据条件输出 
	if(cnt!=1) printf("Non-Eulerian");
	else{
		if(evenCnt==n)printf("Eulerian");
		else if(oddCnt==2)printf("Semi-Eulerian");
		else printf("Non-Eulerian");
	} 
	return 0;
}