网站建设代理合同,wordpress小工具音乐美化,做网站需要购买什么,自己电脑做服务器搭建网站题目描述#xff1a;Einstein 学起了画画。此人比较懒~~#xff0c;他希望用最少的笔画画出一张画……给定一个无向图#xff0c;包含 n 个顶点#xff08;编号 1∼n#xff09;#xff0c;m 条边#xff0c;求最少用多少笔可以画出图中所有的边。输入格式第一行两个整数…题目描述Einstein 学起了画画。此人比较懒~~他希望用最少的笔画画出一张画……给定一个无向图包含 n 个顶点编号 1∼nm 条边求最少用多少笔可以画出图中所有的边。输入格式第一行两个整数 n, m。接下来 m 行每行两个数 a, ba不等于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 53 31 22 33 1
