题意:给你一个图，问你最少几笔能画完该图，其中孤立的点除外
#include<cstdio>
#include<string.h>
#include<vector>
#include<string>
#define N 100005
#include<algorithm>
#include<iostream>
using namespace std;
int Father[N];
vector<int>a;//记录根节点，其长度为连通分支的个数
int in[N];
int num[N];//每个连通分支奇度顶点的个数。
bool Hash[N];
int n,m;
void init()
{
memset(num,0,sizeof(num));
for(int i=1;i<=n;++i) Father[i]=i;
memset(in,0,sizeof(in));
memset(Hash,false,sizeof(Hash));
a.clear();
}
int Find(int x)
{
if(x==Father[x]) return x;
return Father[x]=Find(Father[x]);
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x!=y) Father[x]=y;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=0;i!=m;++i)
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
in[a]++;
in[b]++;
}
int res=0;
for(int i=1;i<=n;++i)
{
int k=Find(i);
if(!Hash[k])
{
Hash[k]=true;
a.push_back(k);
}
if(in[i]&1) num[k]++;
}
for(int i=0;i<a.size();++i)
{
int k=a[i];
if(!in[k]) continue;
if(num[k]==0) res++;
else res+=num[k]/2;
}
printf("%d\n",res);
}return 0;
}