记录编号	33204	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	1.445 s
提交时间	2011-11-09 18:52:43	内存使用	1.79 MiB

#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

int n,m,tmp,ans,f[100001],num[100001],sum[100001],c[100001];

int dfs(int v)
{
	if(v!=f[v])
		f[v]=dfs(f[v]);
	return f[v];
}

int main()
{
	int i,x,y,tmpx,tmpy;
	ifstream fin("sent.in");
	ofstream fout("sent.out");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		f[i]=i;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		if(x==y)
			continue;
		tmpx=dfs(x);
		tmpy=dfs(y);
		if(tmpx!=tmpy)
			f[tmpx]=y;
		c[x]++;
		c[y]++;
	}
	for(i=1;i<=n;i++)
	{
		tmpx=dfs(i);
		num[tmpx]++;
		if(c[i]%2)
			sum[tmpx]++;
	}
	tmp=0;
	ans=0;
	for(i=1;i<=n;i++)
		if(num[i]>1)
		{
			if(sum[i]>2)
				ans+=(sum[i]-2)/2;
			tmp++;
		}
	fout<<ans+tmp-1<<endl;
	fin.close();
	fout.close();
	return 0;
}