记录编号	72402	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.807 s
提交时间	2013-10-16 22:17:43	内存使用	3.48 MiB

#include<cstdio>
#include<vector>
using namespace std;
int N,M,Ans,outer[100001];
class C
{
public:
	int father,count,odd;
}s[100001];
int find_father(int x)
{
	int tmp,final=x,y=x;
	while(s[final].father!=final)final=s[final].father;
	while(s[y].father!=y)
	{
		tmp=s[y].father;
		s[y].father=final;
		y=tmp;
	}
	return final;
}
void merge(int x,int y)
{
	s[x].count+=s[y].count;
	s[y].count=0;
	s[y].father=s[x].father;
}
int main()
{
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
	int i,j,a,b,fa,fb;
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)s[i].father=i,s[i].count=1,s[i].odd=0;
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		outer[a]++;
		outer[b]++;
		fa=find_father(a);
		fb=find_father(b);
		if(fa!=fb)
		{
			merge(fa,fb);
		}
	}
	for(i=1;i<=N;i++)
		s[find_father(i)].odd+=(outer[i]&1);
	Ans=0;
	for(i=1;i<=N;i++)
		if(s[i].count>1)
		{
			if(s[i].odd>2)Ans+=s[i].odd/2-1;
			Ans++;
		}
	printf("%d\n",Ans-1);
	/*
	Ans=0;
	for(i=1;i<=N;i++)
	if(!boo[i])
	{
		//printf("%d\n",i);
		if(i>1)Ans++;
		j=dfs(i);
		if(j>2)Ans+=(j/2-1);
		//if(j>2)printf("%d\n",j);
	}
	printf("%d\n",Ans);
	*/
	return 0;
}