Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
什么是并查集?
例子:
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
类似上面这种问题,都可以采用并查集来处理。开始的时候每个元素都是一个集合,然后根据一定的关系找到合并的集合,最后进行归类。
基本操作:
初始化init 把每个点所在集合初始化为其自身。
通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。
查找find 查找元素所在的集合,即根节点,find有个小技巧,也就是并查集的路径压缩算法,即在find的过程中直接把子节点指向代表。
合并join 将两个元素所在的集合合并为一个集合。
通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。
解题思路:
这属于并查集的基本题型,可以根据基本的并查集模板求解。
1、至少要修多少道路让所有城市相连;
2、可以判断有多少个城区,保证每个城区中的每个城市都有可以互相连通;
3、若有5个城区就至少要修4条路;
4、有n个至少修n-1条路。
源代码:G++
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<string>
using namespace std;
//该数组表示下标为i的城市那部分城区的中心(例pre[3]=5,表示第3个城市的中心为第5个城市)
int pre[1005];
//初始化,最开始的时候每个城市的中心就是自己
void init(int n)
{
int i;
for (i = 1; i <= n; ++i) {
pre[i] = i;
}
}
//用递归函数寻找第x个城市的中心是哪个
int find(int x)
{
//路径压缩算法
if (x != pre[x]) {
//这里只会计算一次,存储在pre[x]中,注意如果数量级很大,不推荐使用递归算法
pre[x] = find(pre[x]);
}
return pre[x];
}
//函数作用:将a,b两个城市归入一个城区
void join(int a, int b)
{
//x,y分别为a,b两个城市所在城区的中心
int x = find(a);
int y = find(b);
if (x != y) {
//将b城市所在城区的中心也变成a城市所在城区的中心,这时候a,b城所在的两个城区就相连了。这两个城区中的每一个城市都有道路可以来往
pre[x] = y;
}
}
int main()
{
int n;
while (~scanf("%d", &n))
{
if (n == 0) break;
int m;
init(n); //初始化
scanf("%d", &m);
int i;
for (i = 1; i <= m; i++)
{
int a, b;
//输入相连的2个城市a,b
scanf("%d%d", &a, &b);
//将a,b连接
join(a, b);
}
//part表示有多少城区
int part = 0;
for (i = 1; i <= n; i++)
{
//如果有个城市的中心是自己,说明这个城市是中心城市。代表这是一个独立的城区,
//因为一个城区的中心只有一个城市。 有多少个中心城市,就有多少个城区。
if (pre[i] == i)
part++;
}
//有n个城区,要让所有城市相连,至少就要多修n-1条路
printf("%d\n", part - 1);
}
return 0;
}