C++11(clang++ 3.9) 解法, 执行用时: 134ms, 内存消耗: 1532K, 提交时间: 2020-05-30 10:59:54

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int p[MAXN];
int find(int x)
{
	return p[x]=p[x]==x?x:find(p[x]);
}
void init()
{
	for(int i=0;i<MAXN;i++)
	p[i]=i;
}
int main()
{
	int N,M;
	while(cin>>N>>M)
	{
		vector<bool> exist(N+1);
		vector<int> deg(N+1);
		init();
		while(M--)
		{
			int u,v;
			cin>>u>>v;
			exist[u]=exist[v]=true;
			deg[u]++,deg[v]++;
			int pu=find(u),pv=find(v);
			if(pu!=pv) p[pu]=pv;
		}
		vector<int> cnt(N+1);
		for(int i=1;i<=N;i++)
		if(exist[i])
		{
			if(deg[i]%2) cnt[find(i)]++;
		}
		int tot=0;
		for(int i=1;i<=N;i++)
		if(exist[i]&&i==find(i))
		{
			if(cnt[i]==0) tot++;
			else tot+=cnt[i]/2;
		}
		cout<<tot<<endl;
	}
}