题目描述

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

输入输出格式

输入格式:

第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M

随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号

注意:两个城市连接多条公路是合法的

输出格式:

至少还需建立多少条路

输入输出样例

输入样例#1: 复制

3 3
1 2
1 3
2 3
输出样例#1: 复制

0
输入样例#2: 复制

3 3
1 2
1 2
2 1
输出样例#2: 复制

1

说明

对于30%的数据,1<=N<=10

对于70%的数据,1<=N<=200

对于100%的数据,1<=N<=1000,1<=M<=1000

思路:并查集。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans;
int fa[],vis[];
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
int dx=find(x);
int dy=find(y);
if(dx==dy) continue;
fa[dy]=dx;
}
for(int i=;i<=n;i++)
if(!vis[find(i)]) vis[find(i)]=,ans++;
cout<<ans-;
}

最新文章

  1. [WinAPI] 获取窗口句柄的几种方法
  2. jquery控制radio选中
  3. Android笔记——我的Android课的开始
  4. PHP条件语句语法与示例
  5. Linux文件查看/编辑方法介绍
  6. codeforces round #234B(DIV2) C Inna and Huge Candy Matrix
  7. A trip through the Graphics Pipeline 2011_12 Tessellation
  8. 15、C#基础整理(递归)
  9. UIApplication介绍
  10. 二维码开源库zbar、zxing使用心得
  11. vimrc 留备份
  12. linux一键安装vncserver脚本
  13. PHP入门-摘要表格处理问题
  14. bzoj千题计划165:bzoj5127: 数据校验
  15. WebService详解(二)
  16. 创建物理卷报错Can&#39;t open /dev/sdb5 exclusively. Mounted filesystem的问题解决过程记录
  17. Android进程和线程(Android开发指南--译)
  18. Android蓝牙通信功能开发
  19. Flink-on-yarn
  20. 【BZOJ】2301: [HAOI2011]Problem b

热门文章

  1. CTSC2012 熟悉的文章 广义后缀自动机_单调队列
  2. iOS开发——Block使用小结
  3. 15条JavaScript最佳实践【转】
  4. [BZOJ3673&amp;3674]可持久化并查集&amp;加强版
  5. 关于python 中的偏函数转载
  6. C指针思考-(1)
  7. django orm 基本
  8. C#调用带结构体指针的C Dll的方法
  9. wget 升级
  10. vjudge A - Beautiful numbers