【华为OD机试B卷】服务器广播、需要广播的服务器数量(C++/Java/Python)
CSDN 2024-06-26 13:37:01 阅读 98
题目
题目描述
服务器连接方式包括直接相连,间接连接。
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;
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)
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。