#蓝桥#JAVA#合根植物
题目描述
w星球的一个种植园，被分成m×n个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入描述
第一行，两个整数m,n用空格分开，表示格子的行数、列数（1≤m,n≤1000）。
接下来一行，一个整数k(0≤k≤)，表示下面还有k行数据。
接下来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
输出描述
输出植物数量。
解题思路
该程序的核心目标是借助并查集算法，处理不相交集合的合并与查询问题。假定存在一个由 n 行 m 列格子所构成的区域，每个格子都能被视作一个独立的集合。通过 k 次合并操作，把某些格子所属的集合合并起来，最终输出合并操作完成后，剩余的独立集合数量。
1. 初始化
-
输入读取：借助
Scanner类从标准输入读取三个整数n、m和k。这里的n和m代表区域的行数与列数，k则表示后续要进行的合并操作次数。 -
连通分量数量初始化：初始状态下，每个格子都是一个独立的集合，所以连通分量的数量为
n * m，将其赋值给变量count。 -
并查集数组初始化：创建一个长度为
n * m + 1的数组p，数组索引从 1 开始。把数组中每个元素的父节点初始化为其自身，即p[i] = i，这表明每个元素最初都属于一个独立的集合。
2. 合并操作
-
循环处理：通过
while(k-- > 0)循环，执行k次合并操作。在每次循环里，读取两个整数a和b，代表要将这两个格子所属的集合进行合并。 -
查找根节点：调用
find方法分别找出a和b所在集合的根节点roota和rootb。find方法采用递归的方式查找根节点，并且在查找过程中进行路径压缩，也就是把当前节点的父节点直接设置为根节点，这样能提高后续查找的效率。 -
合并集合：若
roota和rootb不相等，说明a和b处于不同的集合，此时将rootb的父节点设置为roota，实现两个集合的合并。同时，连通分量的数量count减 1。
3. 输出结果
合并操作全部完成后，输出最终的连通分量数量 count，这个数量代表了经过合并操作后，剩余的独立集合数量。
代码展示
import java.util.Scanner;public class Main {// 定义一个静态数组 p，用于存储并查集的父节点信息static int[] p;// 定义一个静态变量 count，用于记录并查集中连通分量的数量static int count;public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 在此输入您的代码...// n 和 m 可能代表某种矩阵或区域的行数和列数// k 表示接下来要进行的合并操作的次数int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();// 初始化连通分量的数量，初始时每个元素都是一个独立的连通分量，所以数量为 n * mcount = n * m;// 初始化并查集数组 p，数组大小为 n * m + 1，索引从 1 开始p = new int[n * m + 1];// 初始化并查集，将每个元素的父节点初始化为自身for(int i = 1; i <= n * m; i++){p[i] = i;}// 循环 k 次，每次读取两个整数 a 和 b，表示要将这两个元素所在的连通分量合并while(k-- > 0){int a = sc.nextInt();int b = sc.nextInt();// 调用 connect 方法将 a 和 b 所在的连通分量合并connect(a, b);}// 输出最终的连通分量数量System.out.println(count);// 关闭 Scanner 对象，释放资源sc.close();}// 查找元素 x 所在连通分量的根节点，并进行路径压缩public static int find(int x){// 如果 x 的父节点不是它本身，说明 x 不是根节点if(p[x] != x){// 递归查找 x 的父节点的根节点，并将 x 的父节点直接设置为根节点，实现路径压缩p[x] = find(p[x]);}// 返回 x 所在连通分量的根节点return p[x];}// 合并元素 a 和 b 所在的连通分量public static void connect(int a, int b){// 查找 a 所在连通分量的根节点int roota = find(a);// 查找 b 所在连通分量的根节点int rootb = find(b);// 如果 a 和 b 所在的连通分量的根节点不同，说明它们属于不同的连通分量if(roota != rootb){// 将 b 所在连通分量的根节点的父节点设置为 a 所在连通分量的根节点，实现合并p[rootb] = roota;// 合并后，连通分量的数量减 1count--;}}
}
