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

题目

实现代码

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)