题目

题目描述

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

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

输出

3

说明

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

用例二

输入

1 11 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 sysdef 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 += 1count = 0str = 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]*nfor i in range(n):    if not visited[i]:        dfs(arr, visited, i)print(count)