欧拉回路的使用&&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;}