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

题目部分

---

解读与分析

题目解读：

在矩阵中，直接连接的服务器用 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 usedNumber = new HashSet();
		List> connectionList = new ArrayList>();
		
		for( int i = 0; i < numbers.length; i ++ )
		{
			if( usedNumber.contains( i ) )
			{
				continue;
			}
			Set newConnectionSet = new HashSet();
			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 usedNumber, Set 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);
    }
}

(完)