hdu 3018 Ant Trip

点击打开链接hdu 3018

题意: 给定一个n个点m条边的无向图求有几条欧拉道路或者欧拉回路
思路: 欧拉回路
分析:
1 给定一个图判断欧拉道路的条数，那么对于一个图有n个连通分支来说那么至少有n条欧拉道路或者欧拉回路
2 那么我们首先应该利用并查集来求出有几个连通分支
3 求出有几个连通分支后，我们就要去求每一个连通分支里面有几条欧拉道路或者欧拉回路，那么很明显是通过度数来判断，如果度数都是偶数那么当前的连通分支就是一个欧拉回路，那么如果有奇数点，那么欧拉道路的个数就是(奇数点个数+1)/2

代码:

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

const int MAXN = 100010;
int n , m;
int degree[MAXN] , father[MAXN] , num[MAXN];
bool vis[MAXN];

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

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

int solve(){
    int ans = 0;
    set<int>s;
    s.clear();
    for(int i = 1 ; i <= n ; i++)
        if(vis[i])
           s.insert(find(i));
    for(int i = 1 ; i <= n ; i++)
       if(degree[i]&1)
          num[find(i)]++;
    set<int>::iterator it;
    for(it = s.begin() ; it != s.end() ; it++){
       if(!num[*it])
          ans++;
       else
          ans += (num[*it]+1)/2;
    }
    return ans;
}

int main(){
    int x , y;
    while(scanf("%d%d" , &n , &m) != EOF){
         init();
         for(int i = 0 ; i < m ; i++){
            scanf("%d%d" , &x , &y);
            degree[x]++;
            degree[y]++;
            vis[x] = true;
            vis[y] = true;
            father[find(x)] = find(y);
         }
         printf("%d\n" , solve());
    }
    return 0;
}