HDU 3108 Ant Trip
Ant Trip
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3524 Accepted Submission(s):
1393
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.
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.
to form to achieve their goal.
1 2
2 3
1 3
4 2
1 2
3 4
2
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.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,tot,ans;
int vis[];
int fa[],num[];
int into[],du[];
int find(int x){
if(fa[x]==x) return fa[x];
else return fa[x]=find(fa[x]);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
tot=;ans=;
memset(du,,sizeof(du));
memset(vis,,sizeof(vis));
memset(num,,sizeof(num));
memset(into,,sizeof(vis));
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
into[x]++;into[y]++;
int dx=find(x);int dy=find(y);
if(dx!=dy) fa[dy]=dx;
}
for(int i=;i<=n;i++){
int now=find(i);
if(!vis[now]){
vis[now]=;
num[++tot]=now;
}
if(into[i]%!=) du[now]++;
}
for(int i=;i<=tot;i++){
if(into[num[i]]==) continue;
if(du[num[i]]==) ans++;
ans+=du[num[i]]/;
}
cout<<ans<<endl;
}
}
最新文章
- CSS选择器 转
- 给flash添加A链接
- 【转】如何在Mac系统中安装R的rattle包
- Mysql Innodb 间隙锁浅析
- css中一些必要的公共样式
- &;,引用复制@,忽略错误提示
- 点的双联通+二分图的判定(poj2942)
- 转 SQL Union和SQL Union All两者用法区别效率以及与order by 和 group by配合问题
- Engine许可初始化 - gis开发初步
- What&#39;s DB2 模式?
- PHP Predefined Interfaces 预定义接口(转)
- tomcat安装启动startup.bat文件命令行界面出现乱码的问题解决
- Node.js与Sails~redis组件的使用
- 第一章 Java语言概述1
- translate.py
- ABBYY FineReader 12使用教程
- [osg]osg窗口显示和单屏幕显示
- mvn cli 搭建项目架构
- nginx配置文件中location说明
- linux环境上运行.net core 初探