并查集水题。
一个图存在欧拉回路的判断条件：
无向图存在欧拉回路的充要条件
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都是偶数且该图是连通图。
有向图存在欧拉回路的充要条件
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图
1.每次加点都对两个点的度数加1
2.加点时如果两点不在同一集合，则合并两点所在集合。
3.最后统计每个点度数是否为偶数，并且判断连不连通。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 1100 int du[N];
int fa[N]; void makeset(int n)
{
for(int i=;i<=n;i++)
{
fa[i] = i;
}
} int findset(int x)
{
if(x != fa[x])
{
fa[x] = findset(fa[x]);
}
return fa[x];
} void unionset(int a,int b)
{
int x = findset(a);
int y = findset(b);
if(x != y)
{
fa[x] = y;
}
} int main()
{
int n,m,i;
int a,b;
while(scanf("%d",&n)!=EOF && n)
{
memset(du,,sizeof(du));
makeset(n);
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
du[a]++;
du[b]++;
unionset(a,b);
}
int flag = ;
int cnt = ;
for(i=;i<=n;i++)
{
if(fa[i] == i)
cnt++;
}
if(cnt>=)
flag = ;
if(flag){
for(i=;i<=n;i++)
{
if(du[i]% != )
{
flag=;
break;
}
}
}
if(flag)
cout<<<<endl;
else
cout<<<<endl;
}
return ;
}