<span>HDU3018 Ant Trip</span>

#include <iostream>
using namespace std;
const int M=100000+10;
int gree[M];
int father[M];
int rank1[M];
int save[M];
bool used[M];
bool mark[M];
void Make_Set(int x)
{
    father[x]=x;
    rank1[x]=0;
}
int Find(int x)
{
    int k=0;
    while(x!=father[x])
    {
        save[k++]=x;
        x=father[x];
    }
    for(int j=0; j<k; j++)
        father[save[j]]=x;
    return x;
}
void Union(int a,int b)
{

    int x=Find(a);
    int y=Find(b);
    if(x==y) return;
    if(rank1[x]<rank1[y]) father[x]=y;
    else
    {
        father[y]=x;
        if(rank1[x]==rank1[y]) rank1[x]++;
    }
}
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        memset(gree,0,sizeof(gree));
        memset(used,0,sizeof(used));
        memset(mark,0,sizeof(mark));
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if (!used[a])
            {
                used[a]=1;
                Make_Set(a);
            }
            if (!used[b])
            {
                used[b]=1;
                Make_Set(b);
            }
            gree[a]++;
            gree[b]++;
            Union(a,b);
        }
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            if(used[i]&&gree[i]%2==1)
            {
                if(mark[Find(i)]==0) mark[Find(i)]=1;//标记该块已经有奇数点了
                ans++;//计算总奇数点
            }
        }
        ans/=2;//累加，看有多少块没奇数点。。。mark[老大]==0没有奇数点
        for(int i = 1; i <= n; i++)
            if(used[i]&&father[i]==i&&mark[i]==0) ans++;
        printf("%d\n",ans);
    }
    return 0;
}