【华为OD机试B卷】服务器广播、需要广播的服务器数量（C++/Java/Python）
标题[size=3
]标题形貌
服务器连接方式包罗直接相连，间接连接。
A和B直接连接，B和C直接连接，则A和C间接连接。
直接连接和间接连接都可以发送广播。
给出一个N*N数组，代表N个服务器，
matrix =
;=
; 1
，
则代表i和j直接连接࿱
b;不等于 1
时，代表i和j不直接连接。
matrix =
;=
; 1
，
即自己和自己直接连接。matrix =
;=
; matrix。
计算初始需要给几台服务器广播， 才可以使每个服务器都收到广播。
[size=3
]输入
输入为N行，每行有N个数字，为0或1
，由空格分隔，
构成N*N的数组，N的范围为 1
<=
; N <=
; 40
[size=3
]输出
输出一个数字，为需要广播的服务器的数量
[size=1
]
[size=3
]用例一
输入
1
0 0
0 1
0
0 0 1
输出
3
说明
3
台服务器互不连接，所以需要分别广播这 3
台服务器
[size=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 =
; true; bool flag =
; true; for (int i =
; index +
; 1
; i < arr.size(); i+
;+
;) { if (arr =
;=
; 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(
4; 
4;)) !=
; 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 =
; stoi(str); } for (int i =
; 1
; i < n; i+
;+
;) { getline(cin, input); pos =
; 0; vector<string> s; while ((pos =
; input.find(
4; 
4;)) !=
; 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 =
; stoi(s); } } vector<bool> visited(n, false); for (int i =
; 0; i < n; i+
;+
;) { if (!visited) { 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(
4; 
4;); int n =
; str.length; int[][] arr =
; new int; for(int i =
; 0; i < n; i+
;+
;) { arr =
; Integer.parseInt(str); } for(int i =
; 1
; i < n; i+
;+
;) { String[] s =
; in.nextLine().split(
4; 
4;); for(int j =
; 0; j < n; j+
;+
;) { arr =
; Integer.parseInt(s); } } 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 =
;=
; 1
&& !queue.contains(i)) { dfs(arr, queue, i); } } }} Python
import sysdef dfs(arr, visited, index): visited =
; True flag =
; True for i in range(index +
; 1
, len(arr)): if arr =
;=
; 1
: flag =
; False dfs(arr, visited, i) if flag: global count count +
;=
; 1
count =
; 0str =
; input().split(
4; 
4;)n =
; len(str)arr =
; [*n for _ in range(n)]for i in range(n): arr =
; int(str)for i in range(1
, n): s =
; input().split(
4; 
4;) for j in range(n): arr =
; int(s)visited =
; *nfor i in range(n): if not visited: dfs(arr, visited, i)print(count)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]