HDU 1878 欧拉回路(简单欧拉回路判定)

HDU 1878 欧拉回路(简单欧拉回路判定)

http://acm.hdu.edu.cn/showproblem.php?pid=1878

题意:给你N个点和M条无向边,问你这个图是否存在欧拉回路.

分析:无向图欧拉回路存在<==>图连通且所有点度为偶数

直接用并查集+degree处理即可.

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000+10;
int n,m;
int degree[maxn];
int fa[maxn];
int findset(int i)
{
    if(fa[i]==-1) return i;
    return fa[i]=findset(fa[i]);
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        scanf("%d",&m);
        memset(degree,0,sizeof(degree));
        memset(fa,-1,sizeof(degree));
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            degree[u]++;
            degree[v]++;
            u=findset(u), v=findset(v);
            if(u!=v) fa[u]=v;
        }
        int cnt=0;//计数连通分量
        for(int i=1;i<=n;i++)
            if(findset(i)==i) cnt++;
        if(cnt>1)
        {
            printf("0\n");
            continue;
        }
        cnt=0;//计数奇数度的点
        for(int i=1;i<=n;i++)
            if(degree[i]%2==1) cnt++;
        if(cnt!=0) printf("0\n");
        else printf("1\n");
    }
    return 0;
}