-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy path4_1disjointSetUnion.cpp
More file actions
90 lines (81 loc) · 2.5 KB
/
4_1disjointSetUnion.cpp
File metadata and controls
90 lines (81 loc) · 2.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
并查集(Disjoint Set Union, 又称DSU,算法导论里的不相交集合的数据结构)
例题：
畅通工程
时间限制：1秒 空间限制：65536K
题目：
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。
省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。
问最少还需要建设多少条道路？
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；
随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。
为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
输出描述:
对每个测试用例，在1行里输出最少还需要建设的道路数目。
示例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
思路：
按格式输入->并查集思路存放数据->计算有多少根->按格式输出（根数量-1）
@author:JeriYang
@time:2019
*/
#include <stdio.h>
using namespace std;
#define N 1000 //最大城市数量
int Tree[N];//Tree[i]表示节点i的双亲是谁, -1表示自己为根节点
int FindRoot(int x){ //寻找x所在的树的根节点，并对路径进行压缩
if(Tree[x]==-1) return x;
else{ //递归调用
int ret=FindRoot(Tree[x]);
Tree[x]=ret;//将当前结点的双亲结点设置为查找返回的根结点编号
return ret;
}
}
int main(){
int m, n;
while(scanf("%d", &n)!=EOF && n!=0){ //1.输入判断，城镇数量n
scanf("%d", &m); //已有道路数量m
for(int i=1; i<=n; i++) Tree[i]=-1;//初始化结点都为根
//2.读入已存在道路信息
while(m--){
int x, y;
scanf("%d %d", &x, &y);
x=FindRoot(x);
y=FindRoot(y);
if(x!=y) Tree[y]=x;//不在同一棵树那就合并
}
//3.计算根的数量
int count=0;//统计一下根节点数量
for(int j=1; j<=n; j++){
if(Tree[j]==-1) count++;
}
//4.按格式输出结果
printf("%d\n", count-1);
}
return 0;
}