记录编号	72159	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	vector	是否通过	通过
代码语言	C++	运行时间	0.714 s
提交时间	2013-10-15 21:10:59	内存使用	6.77 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> G[100010];
int f[100010],tt[100010];
int k[100010],num[100010];
bool b[1000010];
int n,m,cnt;

int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
 
int main()
{
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)f[i]=i;
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		int x=find(u);
		int y=find(v);
		if(u==v)continue;
		if(x!=y)f[y]=x;
		k[u]++;
		k[v]++;
	}
	
	for(int i=1;i<=n;++i)
	{
		int x=find(i);
		if(k[i]&1)num[x]++;
		tt[x]++;
	}
	int res=0;
	
	for(int i=1;i<=n;++i)
	{
		if(tt[i]>1)
		{
			if(num[i]>2)
			cnt+=(num[i]-2)/2;
			res++;
		}
	}
	printf("%d\n",res+cnt-1);
	return 0;
}