蓝桥杯历届真题:合根植物
问题描述
w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?输入格式
第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行,从上到下,从左到右编号。
比如:5 * 4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17样例输出
5
样例说明
其合根情况参考下图
简单的并查集应用,并查集主要进行两个操作:合并、查找。
用数组arr[]的下角标表示格子的序号,数组的内容表示该格子的根节点序号。
初始状态下,每个格子的根节点为自己。
对于输入的数据a、b:
- 判断是否属于同一个集合,查找a的根节点序号和b的根节点序号,判断a、b的根节点序号是否相同。
- 相同,不进行合并
- 不相同,进行合并,将b的根节点序号index,对应的数组内容arr[index]修改为a的根节点序号(即统一两个格子的根节点)
import java.util.HashSet;
import java.util.Scanner;
public class Main {
//并查集的应用
private static int[] arr;
public static void main(String[] args) {
int m,n,k;
//存放根节点,Set:一个不包含重复元素的 collection
HashSet<Integer> result = new HashSet<Integer>();
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
n = scanner.nextInt();
arr = new int[m*n+1];
k = scanner.nextInt();
//吸收换行符
scanner.nextLine();
//初始化arr数组
for(int i = 0;i<(m*n+1);i++){
arr[i] = i;
}
for(int i = 0;i<k;i++){
int a = scanner.nextInt();
int b = scanner.nextInt();
// System.out.println("(a,b)="+a+" "+b);
join(a,b);
}
scanner.close();
//记录合并之后整个数组的根节点序号
for(int i = 1;i<(m*n+1);i++){
result.add(root(i));
}
System.out.println(result.size());
}
private static void join(int a, int b) {
//判断a,b根节点是否相同
// System.out.println(a+"、"+b+"的根节点:"+root(a)+" "+root(b));
if (root(a)==root(b)) {
//属于同一集合,不进行合并操作
return ;
}else{
//不属于同一集合,进行合并操作,找到b根节点序号index,修改arr[index]的内容为a根节点序号
arr[root(b)]=root(a);
}
}
//找到序号a的根节点序号,并设置arr[a]=根节点序号
private static int root(int a) {
//如果根节点序号=arr[根节点序号],则a为根节点序号
if (a==arr[a]) {
return arr[a];
}else {
//非根节点则进行下一层递归,并设置arr[a]=根节点序号
arr[a] = root(arr[a]);
}
return arr[a];
}
}