题目描述

Einstein 学起了画画。

此人比较懒~~，他希望用最少的笔画画出一张画……

给定一个无向图，包含 n 个顶点（编号 1∼n），m 条边，求最少用多少笔可以画出图中所有的边。

输入格式

第一行两个整数 n,m。

接下来 m 行，每行两个数 a,b（a=b），表示 a,b 两点之间有一条边相连。

一条边不会被描述多次。

输出格式

一个数，即问题的答案。

输入输出样例

输入 #1

5 5
2 3
2 4
2 5
3 4
4 5

输出 #1

1

说明/提示

对于 50% 的数据，n≤50，m≤100。

对于 100% 的数据，1≤n≤1000，1≤m≤。

分析与思路

分析

本题数据小于,所以暴力方法是不行的,而此时可能有人想到小学学的一笔画问题,但是依然不行,我先带大家回顾一下一笔画问题。

一笔是否能画一张图需要先确定是否为一个联通的图，再数奇数点是否为两个或全为偶数点。(扩展：每两个奇数点需要一笔，总奇数点必为偶数个，能画出总奇数点必为奇数个的图，找我领100RMB)

而本题是一个非连通图，所以要另当别论（考试时能拿分就行），而我则想到了分成几个部分，去进行统计

思路

利用遍历的方法将图分块，再统计每块有多少奇数点。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
vector<int> g[N];
int du[N];
int num[N];
bool st[N];
int b[N];
void dfs(int u,int b1){
	for(int i=0;i<g[u].size();i++){
		if(!st[g[u][i]]){
			b[g[u][i]]=b1;
			st[g[u][i]]=true;
			dfs(g[u][i],b1);
		}
	}
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		num[i]=-1;
		du[i]=0;
		st[i]=false;
	}
	while(m--) {
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
		du[a]++,du[b]++;
	}
	int b1=1;
	for(int i=1;i<=n;i++) {
		if(!st[i]){
			if(g[i].size()>0) num[b1]=0;
			dfs(i,b1);
			b1++;
		}
	}
	for(int i=1; i<=n; i++) {
		if(du[i]%2==1) {
			num[b[i]]++;
		}
	}
	int ans=0;
	for(int i=1;i<b1;i++){
		if(num[i]==0){
			ans++;
		}
		else{
			ans+=num[i]/2;
		}
	}
	cout<<ans;
	return 0;
}