学步园

              题意:

                      给一个无向图..问由最少可以分解成多少个欧拉(通/回)路

              题解:

                      我是觉得首先要找出每一个联通块..在一个联通块中..两个奇数度的点可以构一条通路...虽然不知道怎么证明..感觉上在一个联通块上最少需要的一笔画为其max(1,其奇数度点数/2)...1是因为若此联通块没有奇数度点..也要画一条欧拉回路把该联通块所有边覆盖...

                      直觉还是挺正确的..也是多画了几个图观察出来的..但是有个trick...有些点是独立的..没有边..处理的时候注意.就无视这些点..而不要把这些点也看成联通块了...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<time.h>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
#define MAXM 500005
using namespace std; 
int d[MAXN],father[MAXN],F[MAXN],T[MAXN]; 
bool used[MAXN];
int getfather(int x)
{
       if (father[x]==x) return x;
       return father[x]=getfather(father[x]);   
}
int main()
{        
       int n,m,i,x,y,ans;  
       while (~scanf("%d%d",&n,&m))
       {
               memset(d,0,sizeof(d));
               memset(used,false,sizeof(used));
               for (i=1;i<=n;i++) father[i]=i;
               while (m--)
               {
                       scanf("%d%d",&x,&y);
                       d[x]++,d[y]++;
                       used[x]=used[y]=true;
                       father[getfather(x)]=getfather(y);
               } 
               memset(F,0,sizeof(F)),m=0; 
               for (i=1;i<=n;i++)
                   if (used[i])
                   {
                           if (!F[getfather(i)]) F[father[i]]=++m,T[m]=0;
                           if (d[i]%2) T[F[father[i]]]++; 
                   }
               ans=0;
               for (i=1;i<=m;i++) ans+=max(1,T[i]/2);
               printf("%d\n",ans);
       }
       return 0;
}