首页 > 其他 > 详细

洛谷P1636学画画

时间:2019-04-17 21:13:59      阅读:123      评论:0      收藏:0      [点我收藏+]

传送

这个题我们需要一个大胆的想法(虽然AC后看了题解知道这是个定理)

(求证明qwq)

如果一个图有2或0个奇点,它就一定可以一笔画出,如果不是2或0个奇点,那答案就是奇点数/2

(私认为因为两个奇点确定一条边,所以答案是奇点数/2)

代码就出来了:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,bian[10001][10001],x,y,js[1001];
int main()
{   int jjs=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {scanf("%d%d",&x,&y);
     bian[x][y]=1;
     bian[y][x]=1;
     js[x]++;
     js[y]++;
    }
    for(int i=1;i<=n;i++)
      {if(js[i]%2==1)jjs++;
      //printf("js[%d]=%d\n",i,js[i]);
      }
    if(jjs==2||jjs==0)
    {printf("1\n");return 0;
    }
    int ans=jjs/2;
    printf("%d",ans);
}

 

洛谷P1636学画画

原文:https://www.cnblogs.com/lcez56jsy/p/10726170.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!