华为OD机试 - 发广播 - 并查集(Java 2023 B卷 200分)

发布时间:2023年12月23日

在这里插入图片描述

华为OD机试 2023B卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷)》

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

某地有N个广播站,站点之间有些有连接,有些没有。

有连接的站点在接受到广播后会互相发送。

给定一个N*N的二维数组matrix,数组的元素都是字符"0"或者"1"。

Matrix[i][j]="1"代表i和j站点之间有连接,matrix[i][j]="0"代表没连接。

现在要发一条广播,问初始最少给几个广播站发送,才能保证所有的广播站都收到消息。

二、输入描述

从stdin输入,共一行数据,表示二维数组的各行,用逗号分隔行。保证每行字符串所合的字符数一样的。

三、输出描述

返回初始最少需要发送广播站个数。

例如:

1、输入

110,110,001

2、输出

2

3、说明

站点1和站点2有直接连接,站点3和站点1和站点2没有直接连接,所以开始至少需要两个站点的广播。

四、并查集

并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。并查集的主要操作包括合并两个集合以及查询元素所属集合。

并查集的具体实现通常是通过一个父节点数组来实现的,数组中的每个元素都指向它的父节点。在初始化时,每个元素都是自己的父节点,表示它们各自构成一个单独的集合。当需要合并两个集合时,将一个集合的根节点的父节点指向另一个集合的根节点,从而将它们连接起来。在查询元素所属集合时,只需要通过不断查找父节点的方式,找到元素的根节点,即所在集合的代表元素。

并查集的主要应用包括解决连通性问题、最小生成树等问题。在信息学的国际国内赛题中,也常常出现需要使用并查集来解决的问题。这类问题的特点是数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间内计算出试题需要的结果,只能用并查集来描述。

Java 实现并查集

public class UnionFind {  
    private int[] parent; // 用于存储每个元素的父节点  
    private int[] rank; // 用于存储每个元素所在集合的大小(秩)  
  
    // 构造方法,初始化并查集  
    public UnionFind(int n) {  
        parent = new int[n];  
        rank = new int[n];  
        for (int i = 0; i < n; i++) {  
            parent[i] = i; // 每个元素初始时都是自己的父节点  
            rank[i] = 1; // 每个元素初始时都构成一个单独的集合,集合大小为1  
        }  
    }  
  
    // 查找元素x所在的集合,即找到它的根节点  
    public int find(int x) {  
        if (x != parent[x]) {  
            parent[x] = find(parent[x]); // 路径压缩,将x的父节点直接设为根节点  
        }  
        return parent[x];  
    }  
  
    // 合并元素x和元素y所在的集合  
    public void union(int x, int y) {  
        int rootX = find(x); // 找到元素x的根节点  
        int rootY = find(y); // 找到元素y的根节点  
        if (rootX == rootY) {  
            return; // 如果它们已经在同一个集合中,则无需合并  
        }  
        // 根据两个集合的大小,将小的集合合并到大的集合中,以达到树高最小的效果  
        if (rank[rootX] > rank[rootY]) {  
            parent[rootY] = rootX;  
        } else if (rank[rootX] < rank[rootY]) {  
            parent[rootX] = rootY;  
        } else {  
            parent[rootY] = rootX;  
            rank[rootX]++; // 若两个集合大小相等,则合并后新的集合大小加1  
        }  
    }  
}

以上代码中,使用了一个整型数组parent来存储每个元素的父节点,以及一个整型数组rank来存储每个元素所在集合的大小(秩)。在构造方法中,初始化了这两个数组。在查找操作中,使用了路径压缩技术,将元素的父节点直接设为根节点,以加快查找速度。在合并操作中,根据两个集合的大小,将小的集合合并到大的集合中,以达到树高最小的效果。

五、Java算法源码

public class OdTest02 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] matrix = sc.nextLine().split(",");
        int n = matrix.length;

        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (matrix[i].charAt(j) == '1') {
                    uf.union(i, j);
                }
            }
        }
        System.out.println(uf.count);
    }
}

// 并查集
class UnionFind {
    int[] pre;
    int count;

    /**
     * 初始化
     */
    public UnionFind(int n) {
        pre = new int[n];
        for (int i = 0; i < n; i++) {
            pre[i] = i;
        }
        count = n;
    }

    /**
     * 查找元素 x 的树的根
     */
    public int find(int x) {
        if (x != pre[x]) {
            pre[x] = find(pre[x]);
            return pre[x];
        }
        return x;
    }

    /**
     * 合并
     */
    public void union(int x, int y) {
        int x_pre = find(x);
        int y_pre = find(y);

        if (x_pre != y_pre) {
            pre[y_pre] = x_pre;
            count--;
        }
    }
}

六、效果展示

1、输入

110,110,001

2、输出

2

3、说明

站点1和站点2有直接连接,站点3和站点1和站点2没有直接连接,所以开始至少需要两个站点的广播。

在这里插入图片描述


🏆下一篇:华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分)

🏆本文收录于,华为OD机试(JAVA)真题(A卷+B卷)

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

文章来源:https://blog.csdn.net/guorui_java/article/details/134796234
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。