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

 

分析：

 

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

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

 

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

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

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

 

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

 

1 #include
     
       2 #include
      
        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 }