题面描述

给定一个 $N * N$ 的矩阵，表示 $N$ 台服务器之间的连接关系：

• 如果 $matrix[i][j] == 1$，则表示服务器 $i$ 和服务器 $j$ 直接连接；
• 如果 $matrix[i][j] \neq 1$，则表示服务器 $i$ 和服务器 $j$ 不直接连接；
• 每台服务器与自身直接连接，即 $matrix[i][i] == 1$；
• 矩阵是对称的，即 $matrix[i][j] == matrix[j][i]$。

目标：计算最少需要广播的服务器数量，使得每台服务器都能接收到广播信息。

思路

本题可以转化为图论中的“连通分量”问题：

• 将每台服务器看作图中的一个节点。
• 服务器之间的直接连接看作图中的边。
• 需要找到图中的连通分量数量，每个连通分量需要至少一台服务器广播。

因此，解决本题的步骤如下：

1. 构建图：根据输入的矩阵，构建图的邻接表或邻接矩阵。
2. 遍历图：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历图，统计连通分量的数量。
3. 输出结果：连通分量的数量即为需要广播的服务器数量。

代码分析

• 输入处理：由于题目没有直接给出 $N$ 的值，需要通过读取输入的行数来确定 $N$。每行包含 $N$ 个数字。

• 图的表示：使用邻接矩阵来表示图，其中 matrix[i][j] 表示节点 $i$ 和节点 $j$ 是否直接连接。

• 连通分量的统计：

  • 使用一个布尔数组 visited 来标记每个节点是否被访问过。
  • 遍历每个节点，如果未被访问，则进行一次 DFS/BFS，并将连通分量计数器加一。

• DFS 实现：

  • 递归访问所有与当前节点直接连接且未被访问过的节点。

• 输出结果：最终连通分量的数量即为所需的最少广播服务器数量。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 读取所有输入
    string line;
    vector<vector<int>> matrix;
    while(getline(cin, line)){
        if(line.empty()) continue; // 忽略空行
        vector<int> row;
        int num;
        stringstream ss(line);
        while(ss >> num){
            row.push_back(num);
        }
        matrix.push_back(row);
    }
    int N = matrix.size();
    if(N ==0){
        cout<<0;
        return 0;
    }
    // 检查每行是否有N个元素
    for(auto &row: matrix){
        while(row.size() < N){
            row.push_back(0); // 补全缺失的0
        }
    }
    // 使用DFS统计连通分量
    vector<bool> visited(N, false);
    int count =0;
    // 定义DFS函数
    function<void(int)> dfs = [&](int u)-> void{
        visited[u] = true;
        for(int v=0; v<N; ++v){
            if(matrix[u][v] ==1 && !visited[v]){
                dfs(v);
            }
        }
    };
    for(int i=0; i<N; ++i){
        if(!visited[i]){
            count++;
            dfs(i);
        }
    }
    cout<<count;
}

python

def count_broadcast_servers(matrix):
    N = len(matrix)
    visited = [False] * N
    count = 0

    def dfs(u):
        visited[u] = True
        for v in range(N):
            if matrix[u][v] == 1 and not visited[v]:
                dfs(v)

    for i in range(N):
        if not visited[i]:
            count += 1
            dfs(i)

    return count

# 读取输入
if __name__ == "__main__":
    matrix = []
    try:
        while True:
            line = input().strip()
            if line:
                row = list(map(int, line.split()))
                matrix.append(row)
    except EOFError:
        pass

    # 调用函数并输出结果
    result = count_broadcast_servers(matrix)
    print(result)

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    static boolean[] visited;
    static int count = 0;

    public static void dfs(int u, int[][] matrix) {
        visited[u] = true;
        for (int v = 0; v < matrix.length; v++) {
            if (matrix[u][v] == 1 && !visited[v]) {
                dfs(v, matrix);
            }
        }
    }

    public static int countBroadcastServers(int[][] matrix) {
        int N = matrix.length;
        visited = new boolean[N];
        count = 0;

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                count++;
                dfs(i, matrix);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<int[]> matrixList = new ArrayList<>();

        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                String[] tokens = line.split(" ");
                int[] row = new int[tokens.length];
                for (int i = 0; i < tokens.length; i++) {
                    row[i] = Integer.parseInt(tokens[i]);
                }
                matrixList.add(row);
            }
        }
        
        int[][] matrix = new int[matrixList.size()][];
        for (int i = 0; i < matrixList.size(); i++) {
            matrix[i] = matrixList.get(i);
        }

        // 调用函数并输出结果
        int result = countBroadcastServers(matrix);
        System.out.println(result);
    }
}

题目内容

服务器连接方式包括直接相连，间接相连。$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 <= 40$

输出描述

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

样例1

输入

1 0 0
0 1 0
0 0 1

输出

3

说明

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

样例2

输入

1 1
1 1

输出

1

说明

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