【洛谷P1636】 Einstein学画画

题目描述：

Einstein 学起了画画。

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

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

输入格式

第一行两个整数 n, m。

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

一条边不会被描述多次。

输出格式

一个数，即问题的答案。

分析：

该题为一道欧拉路的题目。

若从起点到终点的路径恰好通过图中每条边一次（起点和终点是不同的点），则该路径称为欧拉路

存在欧拉路的条件：图是连通的，且存在两个奇点。

如果存在两个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。

注意：一个连通图只可能有偶数个奇点

故，若奇点个数为零，则只需一笔，否则需要奇点个数的一半的笔画。

代码：

#include <bits/stdc++.h>
using namespace std;int n, m, a, b, ans, cnt[1010];int main() {scanf("%d %d", &n, &m);for(int i = 1; i <= m; ++i) {scanf("%d %d", &a, &b);cnt[a]++;cnt[b]++;}for(int i = 1; i <= n; ++i)if(cnt[i] % 2 != 0)ans++;if(ans == 0)printf("1");elseprintf("%d", ans / 2);return 0;
}

部分测试数据：

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

3 3
1 2
2 3
3 1