[欧拉回路] hdu 3018 Ant Trip

[欧拉回路] hdu 3018 Ant Trip

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

[欧拉回路] hdu 3018 Ant Trip此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=3018

Ant Trip

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1658    Accepted Submission(s): 641




Problem Description
Ant Country consist of N towns.There are M roads connecting the towns.

Ant Tony,together with his friends,wants to go through every part of the country. 

They intend to visit every road , and every road must be visited for exact one time.However,it may be a mission impossible for only one group of people.So they are trying to divide all the people into several groups,and each may start at different town.Now tony wants to know what is the least groups of ants that needs to form to achieve their goal.



[欧拉回路] hdu 3018 Ant Trip
 


Input
Input contains multiple cases.Test cases are separated by several blank lines. Each test case starts with two integer N(1<=N<=100000),M(0<=M<=200000),indicating that there are N towns and M roads in Ant Country.Followed by M lines,each line contains two integers a,b,(1<=a,b<=N) indicating that there is a road connecting town a and town b.No two roads will be the same,and there is no road connecting the same town.
 


Output
For each test case ,output the least groups that needs to form to achieve their goal.
 


Sample Input
   
   
3 3 1 2 2 3 1 3 4 2 1 2 3 4

 


Sample Output
   
   
1 2
Hint
New ~~~ Notice: if there are no road connecting one town ,tony may forget about the town. In sample 1,tony and his friends just form one group,they can start at either town 1,2,or 3. In sample 2,tony and his friends must form two group.

 


Source
 


Recommend
gaojie   |   We have carefully selected several similar problems for you:  
3013 
3015 
3016 
3011 
3010 
 




Statistic | 
Submit | 
Discuss | 
Note

题目意思:

给一幅无向图,求要用多少次一笔画,把全部边走完,边仅仅能走一次。孤立点不算。

解题思路:
dfs把每一个连通块找到,然后统计奇数度数节点个数。

注意孤立节点不算。

代码:

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 110000
int de[Maxn],n,m;
vector<vector<int> >myv;
int in[Maxn],cnt;
bool vis[Maxn];

void dfs(int cur)
{
    in[++cnt]=cur;
    vis[cur]=true;
    for(int i=0;i<myv[cur].size();i++)
    {
        int ne=myv[cur][i];
        if(vis[ne])
            continue;
        dfs(ne);
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   while(~scanf("%d%d",&n,&m))
   {
       myv.clear();
       myv.resize(n+10);
       memset(de,0,sizeof(de));

       for(int i=1;i<=m;i++)
       {
           int a,b;
           scanf("%d%d",&a,&b);
           myv[a].push_back(b);
           myv[b].push_back(a);
           de[a]++;
           de[b]++;
       }
       memset(vis,false,sizeof(vis));

       int ans=0;

       for(int i=1;i<=n;i++)
       {
           if(!vis[i])
           {
               cnt=0;
               dfs(i);
               int temp=0;
               if(cnt==1)  //孤立节点不算
                    continue;
               for(int j=1;j<=cnt;j++)
               {
                   if(de[in[j]]&1)
                        temp++;
                    //printf("i:%d j")
               }
               if(!temp)
                    ans++;
               else
                    ans+=temp/2;
           }
       }
       printf("%d\n",ans);

   }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117913.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Mysql横向分组统计

    Mysql横向分组统计

  • APP运营:盘点八款主流 APP 消息推送工具[通俗易懂]

    APP运营:盘点八款主流 APP 消息推送工具[通俗易懂]在APP日常运营中,基于营销以及推广的目的,我们需要对APP用户推送一些活动信息或重要资讯。常见的消息推送工具分为两种:1、即技术团队自行开发;2、第三方Push工具对于许多创业型公司而言,相对于自行开发,第三方消息推送工具在推送稳定性、精确覆盖性以及成本方面更具有优势,只需要下载并集成SDK就可以实现功能。本文中我们将盘点八款主流第三方APP消息推送工具,希望对大家在A…

  • datagrip激活码20213月最新在线激活

    datagrip激活码20213月最新在线激活,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 二叉树的层序遍历(两种方法实现)

    二叉树的层序遍历(两种方法实现)两种方法实现二叉树的层序遍历1、说明二叉树的层序遍历是面试经常会被考察的知识点,甚至要求当场写出实现过程。层序遍历所要解决的问题很好理解,就是按二叉树从上到下,从左到右依次打印每个节点中存储的数据。如下图:先序遍历:A→B→D→C中序遍历:B→D→A→C后续遍历:D→B→C→A层序遍历:A→B→C→…

  • pycharm2022.01.12临时激活码[最新免费获取]

    (pycharm2022.01.12临时激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~0H…

  • 如何写好单元测试:Mock脱离数据库+不使用@SpringBootTest「建议收藏」

    如何写好单元测试:Mock脱离数据库+不使用@SpringBootTest「建议收藏」目录1、一般的单元测试写法2、单元测试步骤3、对一般的单元测试写法分析优化4、最佳的单元测试写法:Mock脱离数据库+不启动Spring+优化测试速度+不引入项目组件一、普遍的单元测试方法作为一个Java后端程序员,肯定需要写单元测试。我先提供一个典型的错误的单元测试例子:@RunWith(SpringRunner.class)@SpringBootTest(cla…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号