Ant Trip （HDU3018）欧拉图

                                                            Ant Trip

题目链接：Click Here~

题目分析：

     题目说题目给出n座城市，m条路。然后有一群蚂蚁想分成最少的组数，就可以走完m条路。题目要求每条路只能有一组蚂蚁通过。要求求出要走完这m条路的最少蚂蚁组数。

算法分析：

    很显然是一道明显的欧拉图问题，如果存在欧拉回路或者欧拉路径是则一组蚂蚁就可以直接走完。但是当不是欧拉图的时候，而是其他连通集的时候就要特别的判断了。所以求解问题的步骤可以有以下两大部组成。

一、欧拉图条件

   1、欧拉回路：图是连通的且所有顶点的度数均为偶数。

   2、欧拉路径：图是连通的且除了起点和终点外其他的顶点度数均为偶数。

二、连通集

   用并查集来判断图的连通性

   如果图是连通集，则要走完该连通集，需要的步数为所有的奇数度数顶点个数除以二。

总组数 = 欧拉图 + 连通集

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

const int N = 1e5 + 5;
int n,m,odd[N],deg[N],f[N];
vector<int> ive;
bool used[N];
void Init()
{
    ive.clear();
    for(int i = 0;i <= n;++i){
       deg[i] = 0;
       odd[i] = 0;
       used[i] = 0;
       f[i] = i;
    }
}
int Find(int u)
{
    if(u == f[u])
      return f[u];
    else
      return f[u] = Find(f[u]);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        Init();
        int a,b,fa,faa,fab;
        for(int i = 0;i < m;++i){
           scanf("%d%d",&a,&b);
           deg[a]++;
           deg[b]++;
           faa = Find(a);
           fab = Find(b);
           f[fab] = faa;
        }
        //Father will plus also.
        for(int i = 1;i <= n;++i){
           fa = Find(i);
           if(!used[fa]){
              ive.push_back(fa);
              used[fa] = 1;
           }
           if(deg[i]&1) // odd
             odd[fa]++;
        }
        int ans = 0;
        for(int i = 0;i < int(ive.size());++i){
           fa = ive[i];
           if(!deg[fa])      //没路的点
             continue;
           if(!odd[fa])      //欧拉图
             ans++;
           else              //连通集
             ans += odd[fa]/2;  
             /*因为上面记录奇数顶点度数的时候把父亲节点也加上了,
               所以这里就无须加一处理了
             */
        }
        printf("%d\n",ans);
    }
    return 0;
}

Ant Trip （HDU3018）欧拉图

原文：http://blog.csdn.net/zhongshijunacm/article/details/19424491