HDU --- 1878 判断图是否为欧拉回路

题意：这道题讲的是判断所给图中是否存在一个欧拉回路。

知识普及:

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。
欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路。

无向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通；图中只有0个或2个度为奇数的节点
欧拉回路:图连通；图中所有节点度均为偶数

有向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1 或 所有节点入度等于出度
欧拉回路:图连通；所有节点入度等于出度

这道题的思路：利用并查集先判断图连通性，然后利用vis数组记录各点的度.(因为该题是无向图)

判断条件：当一个点的根节点与其他点的根节点不等，则图不连通,输出 0或 当该点的度数是奇数时则非欧拉图，输出 0；其他情况输出 1 .

AC代码如下:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
using namespace std;
int n,m;
int pre[1005],vis[1005];
void init()
{
    for(int i=0;i<=n;i++)
        pre[i]=i;
}

int Find(int x)
{
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}

void un(int x,int y)
{
    int m=Find(x);
    int n=Find(y);
    if(m!=n)
        pre[n]=m;
}
int main()  //抓住这道题的两点,一是存在回路,二是欧拉.
{           //是判断整个图是不是欧拉回路.(不是图中的一部分).
    while(scanf("%d",&n)!=EOF && n){
        scanf("%d",&m);
        init();
        CLR(vis);
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            vis[u]++;
            vis[v]++;
            un(u,v);
        }
        int flag=1;
        for(int i=1;i<n;i++){
            if(pre[i]!=pre[i+1] || vis[i]%2){
                flag=0;
                break;
            }
        }
        if(flag)
            printf("1\n");
        else
            printf("0\n");
    }
}