欧拉回路的使用&&http://acm.hdu.edu.cn/showproblem.php?pid=3018

欧拉回路的应用&&http://acm.hdu.edu.cn/showproblem.php?pid=3018

题意:给你一个图，问你最少几笔能画完该图，其中孤立的点除外

#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;
}