华为OD机考算法题：服务器广播

题目部分

题目	服务器广播
难度	难
题目说明	服务器连接方式包括直接相连，间接连接。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
输出	3
说明	3 台服务器相互不连接，所以需要分别广播这 3 台服务器。
示例2
输入	1 1  1 1
输出	1
说明	2 台服务器相互连接，所以只需要广播其中一台服务器。

---

解读与分析

题目解读：

在矩阵中，直接连接的服务器用 1 表示，不连接的用 0 表示，连接性是传递的。把相互连接的服务器放到同一个集合中，不连接的服务器在不同的集合中。求一共有多少个集合。

分析与思路：

本题虽标记为“难”，实际很简单。

逐一这个服务器，采用深度或广度遍历，逐一把遍历后连接的服务器放到同一个集合中。最后，集合的个数就是需要广播的服务器台数。

---

代码实现

Java代码

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;/*** 服务器广播* * @since 2023.10.15* @version 0.1* @author Frank**/
public class ServerBroadcastCount {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] strNumbers = input.split(" ");int count = strNumbers.length;int[][] numbers = new int[count][count];for (int i = 0; i < count; i++) {if (i != 0) {// 首行已读取input = sc.nextLine();strNumbers = input.split(" ");}int[] lineNum = new int[count];for (int j = 0; j < count; j++) {lineNum[j] = Integer.parseInt(strNumbers[j]);}numbers[i] = lineNum;}processServerBroadcastCount(numbers);}}private static void processServerBroadcastCount( int numbers[][] ){Set<Integer> usedNumber = new HashSet<Integer>();List<Set<Integer>> connectionList = new ArrayList<Set<Integer>>();for( int i = 0; i < numbers.length; i ++ ){if( usedNumber.contains( i ) ){continue;}Set<Integer> newConnectionSet = new HashSet<Integer>();usedNumber.add( i );newConnectionSet.add( i );initConnectionSet( i, usedNumber, newConnectionSet, numbers);connectionList.add(newConnectionSet );}System.out.println( connectionList.size() );}private static void initConnectionSet(int idx, Set<Integer> usedNumber, Set<Integer> newConnectionSet,int numbers[][]) {for( int i = 0; i < numbers.length; i ++ ){if( i == idx ){continue;}int idxCheck = numbers[idx][i];if( usedNumber.contains( i ) || idxCheck == 0 ){continue;}usedNumber.add( i );newConnectionSet.add( i );initConnectionSet( i, usedNumber, newConnectionSet, numbers);}}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var strNumbers = line.split(" ");var count = strNumbers.length;var numbers = new Array();for (var i = 0; i < count; i++) {if (i != 0) {// 首行已读取line = await readline()strNumbers = line.split(" ");}var lineNum = new Array();for (var j = 0; j < count; j++) {lineNum[j] = parseInt(strNumbers[j]);}numbers[i] = lineNum;}processServerBroadcastCount(numbers);}
}();function processServerBroadcastCount(numbers) {var usedNumber = new Set();var connectionList = new Array();for (var i = 0; i < numbers.length; i++) {if (usedNumber.has(i)) {continue;}var newConnectionSet = new Set();usedNumber.add(i);newConnectionSet.add(i);initConnectionSet(i, usedNumber, newConnectionSet, numbers);connectionList.push(newConnectionSet);}console.log(connectionList.length);
}function initConnectionSet(idx, usedNumber, newConnectionSet,numbers) {for (var i = 0; i < numbers.length; i++) {if (i == idx) {continue;}var idxCheck = numbers[idx][i];if (usedNumber.has(i) || idxCheck == 0) {continue;}usedNumber.add(i);newConnectionSet.add(i);initConnectionSet(i, usedNumber, newConnectionSet, numbers);}
}

(完)