洛谷 P2839 畅通工程
2024-08-31 15:42:44
题目描述
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
输入输出格式
输入格式:
第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M
随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号
注意:两个城市连接多条公路是合法的
输出格式:
至少还需建立多少条路
输入输出样例
说明
对于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-;
}
最新文章
- [WinAPI] 获取窗口句柄的几种方法
- jquery控制radio选中
- Android笔记——我的Android课的开始
- PHP条件语句语法与示例
- Linux文件查看/编辑方法介绍
- codeforces round #234B(DIV2) C Inna and Huge Candy Matrix
- A trip through the Graphics Pipeline 2011_12 Tessellation
- 15、C#基础整理(递归)
- UIApplication介绍
- 二维码开源库zbar、zxing使用心得
- vimrc 留备份
- linux一键安装vncserver脚本
- PHP入门-摘要表格处理问题
- bzoj千题计划165:bzoj5127: 数据校验
- WebService详解(二)
- 创建物理卷报错Can&#39;t open /dev/sdb5 exclusively. Mounted filesystem的问题解决过程记录
- Android进程和线程(Android开发指南--译)
- Android蓝牙通信功能开发
- Flink-on-yarn
- 【BZOJ】2301: [HAOI2011]Problem b