题目已经告诉如何判断欧拉回路了，剩下的有一点要注意，可能图本身并不连通。
所以这里用并查集来判断图的联通性。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
/*
并查集用来判断图的联通性，有一组样例图是不连通的。。。
*/
const int maxn=;
int degree[]; struct UF{
int father[maxn];
void init(){
for(int i=;i<maxn;i++){
father[i]=i;
}
}
int find_root(int x){
if(father[x]!=x)
father[x]=find_root(father[x]);
return father[x];
}
void Union(int x,int y){
int fx=find_root(x);
int fy=find_root(y);
if(fx!=fy)
father[fx]=fy;
}
}uf;
int main()
{
int n,m;
int a,b;
uf.init();
scanf("%d %d",&n,&m);
for(int i=;i<m;i++){
scanf("%d %d",&a,&b);
degree[a]++;
degree[b]++;
uf.Union(a,b);
}
int vis[maxn];
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){
int fa=uf.find_root(i);
vis[fa]=;
}
int graphs=;
for(int i=;i<=n;i++){
if(vis[i]){
graphs++;
}
}
int sum=;
int cnt=;
for(int i=;i<=n;i++){
if(i==)
printf("%d",degree[i]);
else
printf(" %d",degree[i]);
sum+=degree[i];
if(degree[i]%){
cnt++;
}
}
printf("\n");
if(sum% || graphs>){
printf("Non-Eulerian\n");
}
else{
if(cnt==)
printf("Eulerian\n");
else if(cnt==)
printf("Semi-Eulerian\n");
else
printf("Non-Eulerian\n");
}
return ;
}