首页 > 代码库 > luoguP1636 Einstein学画画 x
luoguP1636 Einstein学画画 x
P1636 Einstein学画画
题目描述
Einstein学起了画画，
此人比较懒～～，他希望用最少的笔画画出一张画。。。
给定一个无向图，包含n 个顶点(编号1~n)，m 条边，求最少用多少笔可以画出图中所有的边
输入输出格式
输入格式：
第一行2个数n,m
以下m行 每行2个数a,b(a<>b) 表示a,b两点之间有一条边相连
一条边不会被描述多次
输出格式：
一个数 即问题的答案
输入输出样例
输入样例#1：
5 52 32 42 53 44 5
输出样例#1：
1
说明
约定 50%的数据n<=50,m<=100
100%的数据n<=1000,m<=100000
思路:
显而易见，一笔画问题
坑点:
当没有入度为奇数个的点时，直接输出1
代码:
#include <iostream>#include <cstdio>#include <cmath>using namespace std;const int N = 10010;int n,m,start,gs;int du[N];int main(){ scanf("%d%d",&n,&m); for(int i=1,a,b;i<=m;i++) { scanf("%d%d",&a,&b); du[a]++,du[b]++; } for(int i=1;i<=n;i++) { if(du[i]%2!=0) gs++; } if(!gs) printf("1"); else printf("%d",gs>>1); return 0;}
luoguP1636 Einstein学画画 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。