hdu 1878 欧拉回路

点击打开链接hdu 1878

思路: 欧拉回路
分析:
1 首先题目给定的是一个无向图，所以我们判断该图是欧拉图的条件是图是否是连通的并且所有点的度都是偶数
2 很明显度数很好判断，而图是否连通通过并查集

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1010;
int father[MAXN] , degree[MAXN];
int n , m;

void init(){
     memset(degree , 0 , sizeof(degree));
     for(int i = 1 ; i <= n ; i++)
         father[i] = i;
}

int find(int x){
    if(x != father[x]) 
       father[x] = find(father[x]);
    return father[x]; 
}

bool isOk(){
    int root = -1;
    for(int i = 1 ; i <= n ; i++){
       if(degree[i]&1)    
          return false; 
       if(degree[i]){
          if(root == -1) 
             root = find(i);
          else{
             if(root != find(i)) 
                return false;
          }
       }
    }
    return true;
}

int main(){
    while(scanf("%d" , &n) && n){
         scanf("%d" , &m); 
         init();
         int x , y;
         for(int i = 0 ; i < m ; i++){
             scanf("%d%d" , &x , &y); 
             degree[x]++;
             degree[y]++;
             father[find(x)] = find(y);
         }
         if(!isOk()) 
            puts("0");
         else
            puts("1");
    }
    return 0;
}