英文网站建设运营,企业网站建设报价单,在线做数据图的网站有哪些,英国跨境电商平台有哪些题目部分
题目服务器广播难度难题目说明服务器连接方式包括直接相连#xff0c;间接连接。A 和 B 直接连接#xff0c;B 和 C 直接连接#xff0c;则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。 给出一个 N * N 数组#xff0c;代表 N 个服务器#xff0c;mat…题目部分
题目服务器广播难度难题目说明服务器连接方式包括直接相连间接连接。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[][] ){SetInteger usedNumber new HashSetInteger();ListSetInteger connectionList new ArrayListSetInteger();for( int i 0; i numbers.length; i ){if( usedNumber.contains( i ) ){continue;}SetInteger newConnectionSet new HashSetInteger();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, SetInteger usedNumber, SetInteger 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);}
} (完)
