最近在读《算法第四版》学习了并查集算法，通过一道题来巩固自己的知识。也希望能帮助到刷这道题的人。 题目链接
题目描述
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
代码
import java
.util
.Scanner
;
public class Main {
static int[] id
;
static int[] sz
;
static int find(int a
) {
return a
== id
[a
] ? a
: find(id
[a
]);
}
static void union(int a
, int b
) {
if (a
== b
) return;
int x
= find(a
), y
= find(b
);
if (sz
[x
] >= sz
[y
]) {
id
[y
] = x
;
sz
[x
] += sz
[y
];
} else {
id
[x
] = y
;
sz
[y
] += sz
[x
];
}
}
public static void main(String
[] args
) {
Scanner sc
= new Scanner(System
.in
);
while (sc
.hasNext()) {
int N
= sc
.nextInt();
if (N
== 0) break;
int M
= sc
.nextInt();
id
= new int[N
+ 1];
sz
= new int[N
+ 1];
for (int i
= 0; i
< id
.length
; i
++) {
id
[i
] = i
;
sz
[i
] = 1;
}
for (int i
= 0; i
< M
; i
++) {
int x
= sc
.nextInt(), y
= sc
.nextInt();
union(x
, y
);
}
int count
=0;
for (int i
= 1; i
<id
.length
; i
++) {
if(i
==id
[i
])count
++;
}
System
.out
.println(count
-1);
}
}
}
