P1636 Einstein学画画

题目描述

Einstein学起了画画，

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

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

输入输出格式

输入格式：

第一行2个数n,m

以下m行每行2个数a,b(a<>b) 表示a,b两点之间有一条边相连

一条边不会被描述多次

输出格式：

一个数即问题的答案

输入输出样例

输入样例#1：

输出样例#1：

说明

约定 50%的数据n<=50,m<=100

100%的数据n<=1000,m<=100000

分析：

一笔画判断：奇点数为2或0或大于2且不被2整除的图

X笔画判断：奇点数为1及2以上的图，奇点数为N，则X=N整除2

本题其实就是考察简单半欧拉图及其扩展定理，设顶点的度数为连接的边数，然后统计所有顶点中度数为奇数的顶点的个数n，则答案一定为n/2。

首先，根据握手定理，所有顶点的度数之和一定为偶数。则奇数顶点的个数一定为偶数。然后每画一笔，最多可以使奇数顶点个数减少两个（或者不减少），所以一定至少要n/2笔，才能把画画完。

有一个特殊情况，即为所有点构成一个环的情况。此时n=0，但实际上需要一笔画完（即欧拉图），所以需要特判一下。

这个题目如果部分点成环了怎么办？？

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int b[10001];
 5 int main()
 6 {
 7     //freopen("in.txt","r",stdin); 
 8     int n,m,i,j,k,geshu=0,x,y;
 9     scanf("%d%d",&n,&m);
10     for (i=1;i<=m;i++)//运用定理
11     {
12     //运用定理 
13     scanf("%d%d",&x,&y);//运用定理
14     b[x]++;//运用定理
15     b[y]++;//运用定理
16     }
17     //运用定理
18     for (i=1;i<=n;i++)
19         if (b[i]%2==1)//判断度数
20             geshu++;
21     if (geshu)
22         printf("%d",geshu/2);
23     else//特判
24         printf("%d",geshu+1);
25 }