当前位置：首页 > news >正文

华为OD机试真题---服务器广播

news 2025/1/5 18:38:58

华为OD机试中的“服务器广播”题目是一个经典的算法问题，通常涉及图论和连通分量的概念。以下是对该题目的详细解析：

一、题目描述

服务器之间可以通过网络进行连接，连接方式包括直接相连和间接连接。给出一个N×N的数组（矩阵），代表N个服务器，matrix[i][j] == 1表示服务器i和服务器j直接连接，matrix[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

输入：

输出：

解释：在这个例子中，服务器0和服务器1直接连接，服务器1和服务器2直接连接，因此服务器0和服务器2间接连接。只需要向其中任意一台服务器发送广播，其他服务器都能接收到。

示例 2

输入

输出

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

示例 3

输入

2
1 1
1 1

输出

说明： 2台服务器相互连接，所以只需要广播其中一台服务器。

四、解题思路

图论建模：将服务器之间的连接关系看作一个图，服务器是图的节点，连接关系是图的边。问题转化为求图中的连通分量个数。
遍历连通分量：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历图，找到所有的连通分量。
计算广播服务器数量：连通分量的个数即为需要广播的服务器数量。因为每个连通分量中的服务器都可以通过广播相互传播信息，所以只需要在每个连通分量中选择一个服务器进行广播即可。
并查集：可以使用并查集实现，并查集（Union-Find）是一种用于处理一些不交集的合并及查询问题的数据结构，它可以高效地解决连通性问题。在“服务器广播”问题中，我们可以使用并查集来找出所有的连通分量，从而确定需要广播的最少服务器数量。

五、代码实现(DFS)

import java.util.Scanner;public class ServerBroadcast {/*** 使用深度优先搜索（DFS）遍历图中的节点* 该方法主要用于找出图中所有相互连通的节点* * @param matrix 代表图的邻接矩阵，matrix[i][j]为1表示节点i和节点j之间有直接连接，为0表示无直接连接* @param visited 一个布尔数组，用于记录图中各节点的访问状态，visited[i]为true表示节点i已被访问* @param node 当前访问的节点编号，从该节点开始进行深度优先搜索*/private static void dfs(int[][] matrix, boolean[] visited, int node) {// 标记当前节点为已访问visited[node] = true;// 遍历图中所有节点for (int i = 0; i < matrix.length; i++) {// 检查当前节点与节点i是否有连接，且节点i未被访问过if (matrix[node][i] == 1 && !visited[i]) {// 递归调用dfs方法，继续深度优先搜索节点idfs(matrix, visited, i);}}}/*** 该方法通过深度优先搜索（DFS）来计算在给定的矩阵中需要广播的服务器数量* 每个服务器可以与其直接相连的服务器共享广播，因此形成一个连通分量* 该方法旨在找出有多少个这样的连通分量，每个连通分量只需一个服务器进行广播** @param matrix 一个二维数组，表示服务器之间的连接关系矩阵*               matrix[i][j] == 1 表示服务器i和服务器j之间有直接连接，否则没有* @return 广播服务器的数量，即矩阵中连通分量的数量*/public static int countBroadcastServers(int[][] matrix) {// 矩阵的长度，即服务器的数量int n = matrix.length;// 一个布尔数组，用于标记服务器是否已经被访问过boolean[] visited = new boolean[n];// 初始化广播服务器的数量为0int broadcastCount = 0;// 遍历每个服务器for (int i = 0; i < n; i++) {// 如果当前服务器尚未被访问过if (!visited[i]) {// 从当前服务器开始进行深度优先搜索，并将搜索过程中访问到的所有服务器标记为已访问dfs(matrix, visited, i);// 每完成一次深度优先搜索，表示找到了一个新的连通分量，广播服务器数量加1broadcastCount++;}}// 返回广播服务器的数量return broadcastCount;}/*** 主函数入口* 该函数读取输入的服务器数量及它们之间的连接情况，计算并输出需要广播的服务器最小数量* @param args 命令行参数*/public static void main(String[] args) {// 创建Scanner对象以读取输入数据Scanner scanner = new Scanner(System.in);// 读取服务器数量int n = scanner.nextInt();// 消耗换行符scanner.nextLine();// 初始化矩阵int[][] matrix = new int[n][n];// 读取矩阵数据for (int i = 0; i < n; i++) {// 分割输入行以获取矩阵每一行的数据String[] line = scanner.nextLine().split(" ");for (int j = 0; j < n; j++) {// 将字符串数据转换为整数并填充到矩阵中matrix[i][j] = Integer.parseInt(line[j]);}}// 计算并输出需要广播的服务器数量int result = countBroadcastServers(matrix);System.out.println(result);// 关闭Scanner对象scanner.close();}
}

代码解释：

DFS方法：dfs方法接受一个二维数组（矩阵）matrix、一个布尔数组visited（用于记录节点是否被访问过）和一个当前节点node作为参数。它递归地访问所有与当前节点直接相连的未访问节点。
计算广播服务器数量的方法：countBroadcastServers方法接受一个二维数组（矩阵）matrix作为参数，并返回需要广播的服务器数量。它使用一个布尔数组visited来跟踪哪些服务器已经被访问过，并初始化广播计数器broadcastCount为0。然后，它遍历所有服务器节点，对每个未访问的节点调用dfs方法，并将广播计数器增加1。
主方法：main方法读取用户输入，包括服务器数量和矩阵数据，然后调用countBroadcastServers方法计算需要广播的服务器数量，并输出结果。

六、代码实现(并查集)

import java.util.Scanner;public class ServerBroadcastUnionFind {// 并查集类static class UnionFind {private int[] parent;// 初始化并查集public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i; // 初始化时，每个节点都是独立的集合，父节点指向自己}}// 查找根节点（路径压缩）public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩，直接连接到根节点}return parent[x];}// 合并两个集合public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY; // 将一个集合的根节点指向另一个集合的根节点，从而合并两个集合}}// 获取连通分量的数量public int countComponents() {int count = 0;for (int i = 0; i < parent.length; i++) {if (find(i) == i) { // 如果节点自己是根节点，说明是一个新的连通分量count++;}}return count;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取服务器数量int n = scanner.nextInt();scanner.nextLine(); // 消耗换行符// 初始化并查集UnionFind uf = new UnionFind(n);// 读取矩阵数据并合并集合for (int i = 0; i < n; i++) {String[] line = scanner.nextLine().split(" ");for (int j = 0; j < n; j++) {if (i != j && Integer.parseInt(line[j]) == 1) { // 注意i != j，避免将节点与自己合并uf.union(i, j);}}}// 计算并输出需要广播的服务器数量（即连通分量的数量）int result = uf.countComponents();System.out.println(result);scanner.close();}
}

代码解释：

并查集类：UnionFind类实现了并查集的基本功能，包括初始化、查找根节点、合并集合和计算连通分量的数量。
初始化并查集：在main方法中，我们首先读取服务器数量n，然后创建一个大小为n的并查集。
读取矩阵数据并合并集合：我们遍历矩阵，对于每个matrix[i][j] == 1且i != j的情况，调用union方法将服务器i和服务器j所属的集合合并。
计算并输出需要广播的服务器数量：最后，我们调用countComponents方法计算连通分量的数量，并输出结果。这个数量就是需要广播的最少服务器数量。

七、运行示例解析

以下是对ServerBroadcast类及其main方法的详细运行示例解析步骤：

1. 初始化

服务器数量：首先，程序通过Scanner读取服务器数量n，这里是3。
矩阵初始化：然后，程序初始化一个n x n的矩阵matrix，用于表示服务器之间的连接关系。

2. 输入矩阵数据

用户输入矩阵的每一行数据，这里输入的是：
```
1 0 0
0 1 0
0 0 1
```

程序将这些数据解析为整数，并填充到matrix中。填充后的矩阵表示如下：

matrix[0][0] = 1, matrix[0][1] = 0, matrix[0][2] = 0
matrix[1][0] = 0, matrix[1][1] = 1, matrix[1][2] = 0
matrix[2][0] = 0, matrix[2][1] = 0, matrix[2][2] = 1

3. 深度优先搜索（DFS）准备

创建一个布尔数组visited，长度为n，用于记录每个服务器是否已被访问。初始时，所有服务器都未被访问，因此visited数组的所有元素都设置为false。

4. 执行DFS并计算连通分量

程序遍历每个服务器（即遍历matrix的每一行和每一列），并对每个未访问的服务器执行DFS。
对于第一个服务器（索引为0），由于它未被访问，程序从它开始进行DFS：
- 标记服务器0为已访问。
- 检查服务器0与所有其他服务器的连接关系：
  - 服务器0与服务器1无连接（matrix[0][1] = 0），因此不继续搜索。
  - 服务器0与服务器2无连接（matrix[0][2] = 0），因此不继续搜索。
- 由于没有进一步的连接，DFS结束，但找到了一个新的连通分量（只包含服务器0）。
接下来，程序检查服务器1（索引为1），它也未被访问：
- 标记服务器1为已访问。
- 检查服务器1与所有其他服务器的连接关系：
  - 服务器1与服务器0无连接（因为0已被访问过，所以这里实际上不会继续搜索，但逻辑上它们无直接连接）。
  - 服务器1与服务器2无连接（matrix[1][2] = 0），因此不继续搜索。
- 同样，DFS结束，找到了另一个新的连通分量（只包含服务器1）。
最后，程序检查服务器2（索引为2），它同样未被访问：
- 标记服务器2为已访问。
- 检查服务器2与所有其他服务器的连接关系，但发现都没有直接连接（或者已经被访问过）。
- DFS结束，找到了最后一个新的连通分量（只包含服务器2）。