【华为OD机试B卷】服务器广播、需要广播的服务器数量（C++/Java/Python）

题目

题目描述

服务器连接方式包括直接相连，间接连接。

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 0 0 0 1 0 0 0 1 

输出

3 

说明

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

用例二

输入

1 1 1 1 

输出

1 

说明

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

实现代码

C++

#include <iostream> #include <vector> using namespace std;  int count = 0;  void dfs(vector<vector<int>>& arr, vector<bool>& visited, int index) {     visited[index] = true;     bool flag = true;     for (int i = index + 1; i < arr.size(); i++) {         if (arr[index][i] == 1) {             flag = false;             dfs(arr, visited, i);         }     }     if (flag) {         count++;     } }  int main() {     string input;     getline(cin, input);     vector<string> str;     size_t pos = 0;     while ((pos = input.find(" ")) != string::npos) {         str.push_back(input.substr(0, pos));         input.erase(0, pos + 1);     }     str.push_back(input);     int n = str.size();     vector<vector<int>> arr(n, vector<int>(n, 0));     for (int i = 0; i < n; i++) {         arr[0][i] = stoi(str[i]);     }     for (int i = 1; i < n; i++) {         getline(cin, input);         pos = 0;         vector<string> s;         while ((pos = input.find(" ")) != string::npos) {             s.push_back(input.substr(0, pos));             input.erase(0, pos + 1);         }         s.push_back(input);         for (int j = 0; j < n; j++) {             arr[i][j] = stoi(s[j]);         }     }     vector<bool> visited(n, false);     for (int i = 0; i < n; i++) {         if (!visited[i]) {             dfs(arr, visited, i);         }     }     cout << count << endl;     return 0; }  

Java

import java.util.*;  public class Main {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         String[] str = in.nextLine().split(" ");         int n = str.length;         int[][] arr = new int[n][n];         for(int i = 0; i < n; i++) {                arr[0][i] = Integer.parseInt(str[i]);         }         for(int i = 1; i < n; i++) {                String[] s = in.nextLine().split(" ");             for(int j = 0; j < n; j++) {                 arr[i][j] = Integer.parseInt(s[j]);             }         }         int count = 0;         Queue<Integer> queue = new LinkedList<>();         for(int i = 0; i < n; i++) {             if(!queue.contains(i)) {                 dfs(arr, queue, i);                 count++;             }         }         System.out.println(count);     }          public static void dfs(int[][] arr, Queue<Integer> queue, int index) {         queue.offer(index);         for (int i = index + 1; i < arr.length; i++) {             if (arr[index][i] == 1 && !queue.contains(i)) {                 dfs(arr, queue, i);             }         }     } } 

Python

import sys  def dfs(arr, visited, index):     visited[index] = True     flag = True     for i in range(index + 1, len(arr)):         if arr[index][i] == 1:             flag = False             dfs(arr, visited, i)     if flag:         global count         count += 1  count = 0 str = input().split(" ") n = len(str) arr = [[0]*n for _ in range(n)] for i in range(n):     arr[0][i] = int(str[i]) for i in range(1, n):     s = input().split(" ")     for j in range(n):         arr[i][j] = int(s[j]) visited = [False]*n for i in range(n):     if not visited[i]:         dfs(arr, visited, i) print(count)