题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1878

题目大意:欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?

解题思路:判断无向图是否存在欧拉回路,判断每个点的度数是否为偶数+并查集确认连通性。

代码:

 #include<iostream>
#include<cstring>
#include<cstdio>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int N=1e3+; int n,m;
int root[N],indeg[N],outdeg[N]; int find(int x){
return root[x]==x?x:root[x]=find(root[x]);
} int main(){
while(scanf("%d",&n)!=EOF){
if(n==)
break;
CLR(indeg,);
CLR(outdeg,);
for(int i=;i<=n;i++)
root[i]=i;
scanf("%d",&m);
int a,b,x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&a,&b);
indeg[b]++;
outdeg[a]++;
x=find(a),y=find(b);
if(x!=y)
root[x]=y;
}
bool flag=true;
int cnt=;
for(int i=;i<=n;i++){
if(find(i)==i)
cnt++;
if((indeg[i]+outdeg[i])%!=){
flag=false;
break;
}
}
if(flag&&cnt==)
puts("");
else
puts("");
}
return ;
}
05-11 19:29