华为OD机试 - 服务器广播 - 矩阵（Java 2024 C卷 200分）

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

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

一、题目描述

服务器连接方式包括直接相连，间接连接。A 和 B 直接连接，B 和 C 直接连接，则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。

给出一个 N * N 数组，代表 N 个服务器，matrix[i][j] == 1，则代表 i 和 j 直接连接；不等于 1 时，代表 i 和 j 不直接连接。
matrix[i][i] == 1，即自己和自己直接连接。matrix[i][j] == matrix[j][i]。

计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

二、输入描述

输入描述输入为 N 行，每行有 N 个数字，为 0 或 1，由空格分隔，构成 N * N 的数组，N 的范围为 1 <= N <= 50。

三、输出描述

输出一个数字，为需要广播的服务器数量。

1、输入

1 0 0
0 1 0
0 0 1

2、输出

3、说明

3 台服务器相互不连接，所以需要分别广播这 3 台服务器。

四、Java算法源码

public class OdTest {
    /**
     * 1 0 0
     * 0 1 0
     * 0 0 1
     * <p>
     * 3
     *
     *  == 1，即自己和自己直接连接。
     *  != 1，不连接
     *
     * 输出一个数字，为需要广播的服务器数量。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] lineArr = sc.nextLine().split(" ");
        int N = lineArr.length;
        // 输入的矩阵
        int[][] matrix = new int[N][N];
        for (int i = 1; i < N; i++) {
            lineArr = sc.nextLine().split(" ");
            int[] tempArr = new int[N];
            for (int j = 0; j < N; j++) {
                tempArr[j] = Integer.parseInt(lineArr[j]);
            }
            matrix[i] = tempArr;
        }

        Set<Integer> usedSet = new HashSet<Integer>();
        List<Set<Integer>> connectionList = new ArrayList<Set<Integer>>();
        for (int i = 0; i < matrix.length; i++) {
            if (usedSet.contains(i)) {
                continue;
            }
            Set<Integer> newConnectionSet = new HashSet<Integer>();
            usedSet.add(i);
            newConnectionSet.add(i);
            initConnectionSet(i, usedSet, newConnectionSet, matrix);
            connectionList.add(newConnectionSet);
        }
        System.out.println(connectionList.size());
    }

    private static void initConnectionSet(int idx, Set<Integer> usedSet, Set<Integer> newConnectionSet, int matrix[][]) {
        for (int i = 0; i < matrix.length; i++) {
            if (i == idx) {
                continue;
            }
            int idxCheck = matrix[idx][i];
            if (usedSet.contains(i) || idxCheck == 0) {
                continue;
            }

            usedSet.add(i);
            newConnectionSet.add(i);
            initConnectionSet(i, usedSet, newConnectionSet, matrix);
        }
    }
}