蓝桥每日打卡-合根植物

JAY.LIN 收录于未分类

2025-03-11 约 1559 字预计阅读 4 分钟

https://bing.ee123.net/img/rand?artid=146187910

蓝桥每日打卡–合根植物

#蓝桥#JAVA#合根植物

题目描述

w星球的一个种植园，被分成m×n个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入描述

第一行，两个整数m,n用空格分开，表示格子的行数、列数（1≤m,n≤1000）。

接下来一行，一个整数k(0≤k≤ $10_{}^{5}$ )，表示下面还有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 * m
        count = 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;
            // 合并后，连通分量的数量减 1
            count--;
        }
    }
}