【九度OJ】题目1012:畅通工程 解题报告
2024-09-06 12:34:13
【九度OJ】题目1012:畅通工程 解题报告
标签(空格分隔): 九度OJ
原题地址:http://ac.jobdu.com/problem.php?pid=1012
题目描述:
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
输入:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
输出:
对每个测试用例,在1行里输出最少还需要建设的道路数目。
样例输入:
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
样例输出:
1
0
2
998
Ways
这个是图论中的并查集的问题,刚开始没有看明白,后来发现我对findRoot理解有错误。
在最重要的findRoot函数中,如果找到了根元素,返回的是当前的跟元素的数值,而不是-1。这样就保证了,即使在刚开始的时候,所有元素都是根元素,但是如果findRoot的话,返回的是这个数的数值,而不是-1,就可以保证不同的元素在不同的数上。
这里一定要区分x和Tree[x]之间的区别。根元素的Tree[x]是-1,其他元素的Tree[x]是对应的根元素的数值。
#include<stdio.h>
#define size 1000
int Tree[size];
int findRoot(int x) {
if (Tree[x] == -1) {//如果找到了根元素
return x;//返回的是当前的跟元素的数值,而不是-1
} else {
int temp = findRoot(Tree[x]);//找到根的值
Tree[x] = temp;//把当前计算的这个值绑到根上
return temp;
}
}
int main() {
int m, n;
while (scanf("%d", &n) != EOF && n != 0) {
scanf("%d", &m);
for (int i = 1; i <= n; i++) {
Tree[i] = -1;//归位
}
while (m-- != 0) {
int a, b;
scanf("%d%d", &a, &b);
int aRoot = findRoot(a);//找到根的值
int bRoot = findRoot(b);
if (aRoot != bRoot) {//不在同一棵树上
Tree[aRoot] = bRoot;//添加到一起
}
}
int answer = 0;
for (int i = 1; i <= n; i++) {
if (Tree[i] == -1) {//单独的树还有answer棵
answer++;
}
}
printf("%d\n", answer - 1);//只需answer-1就可以把这些树连起来
}
return 0;
}
Date
2017 年 3 月 9 日
最新文章
- expect实现自动登录
- hdu 1028 Ignatius and the Princess III 简单dp
- destoon使用中的一些心得
- 节点的创建--对比jQuery与JavaScript 方法
- [学习笔记]设计模式之Flyweight
- apache 配置https(转)
- Boost.Asio基础(五) 异步编程初探
- Developing a Custom Membership Provider from the scratch, and using it in the FBA (Form Based Authentication) in SharePoint 2010
- 201521123005 《java程序设计》 第七周学习总结
- scala学习
- XMLTABLE
- [TCP/IP] 网络层-ARP协议
- Docker 快速验证 HTML 导出 PDF 高效方案
- httpclient cookie使用介绍
- [NPM] Use npx to run commands with different Node.js versions
- STL应用——hdu1702(队列+堆栈)
- TOPOI 测验1320, 问题C: 4410: [CF41D]Pawn 解题报告
- 关于ajaxfileupload的使用方法以及一些问题
- Oracle单个datafile大小的限制
- mysql :库操作
热门文章
- 63. Binary Tree Level Order Traversal II
- Linux— rpm 命令
- 基于Kubernetes实现前后端应用的金丝雀发布
- UE4类型数据自动注册
- MapReduce07 Join多种应用
- admire, admit
- 大数据学习----day27----hive02------1. 分桶表以及分桶抽样查询 2. 导出数据 3.Hive数据类型 4 逐行运算查询基本语法(group by用法,原理补充) 5.case when(练习题,多表关联)6 排序
- mystar01 nodejs MVC 公共CSS,JS设置
- Android 百度地图用法
- jquery的each和js原生for循环性能对比