Description

【题意】原题来自：2009 Multi-University Training Contest 12 - Host by FZU
给你无向图的 N 个点和 M 条边，保证这 M 条边都不同且不会存在同一点的自环边，现在问你至少要几笔才能所有边都画一遍。（一笔画的时候笔不离开纸）

【输入格式】
多组数据，每组数据用空行隔开。
对于每组数据，第一行两个整数 N,M 表示点数和边数。接下去 M 行每行两个整数 a,b，表示 a,b 之间有一条边。

【输出格式】
对于每组数据，输出答案。

【输入样例】
3 3
1 2
2 3
1 3

4 2
1 2
3 4

【输出样例】
1
2

【数据范围与提示】
$1 \le N \le 10^5,0 \le M \le 2\times 10^5,1 \le a,b \le N$

Hint

#include <bits/stdc++.h>
using namespace std;
int f[110000],cntodd[110000],cntsum[110000],rd[110000];
int findfa(int x){ return f[x]=(f[x]==x?f[x]:findfa(f[x]));}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
	memset(rd&#44;0&#44;sizeof(rd));
	for(int i=1;i&lt;=n;i++)f[i]=i;
	for(int i=1;i&lt;=m;i++)
	{
		int x&#44;y;scanf("%d%d"&#44;&amp;x&#44;&amp;y);rd[x]++&#44;rd[y]++;
		f[findfa(x)]=findfa(y);
	}
	memset(cntodd&#44;0&#44;sizeof(cntodd));
	memset(cntsum&#44;0&#44;sizeof(cntsum));
	for(int i=1;i&lt;=n;i++)
	{
		cntsum[findfa(i)]++;
		if(rd[i] &amp; 1)cntodd[findfa(i)]++;
	}
	int ans=0;
	for(int i = 1; i &lt;= n; i++)if(f[i]==i)
	{
		if(cntsum[i]==1) continue;
		if(cntodd[i]==0) ans++;
		else             ans+=cntodd[i] / 2;
	}
	printf("%d\n"&#44;ans);
}
return 0;

}

</p>