做英文的小说网站,威县做网站哪儿便宜,网站建设现状分析,店铺空间设计案例题目 题目描述 服务器连接方式包括直接相连#xff0c;间接连接。 A和B直接连接#xff0c;B和C直接连接#xff0c;则A和C间接连接。 直接连接和间接连接都可以发送广播。 给出一个N*N数组#xff0c;代表N个服务器#xff0c; matrix[i][j] 1#xff0c; 则代表i和j直…题目 题目描述 服务器连接方式包括直接相连间接连接。 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(vectorvectorint arr, vectorbool 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);vectorstring 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();vectorvectorint arr(n, vectorint(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;vectorstring 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]);}}vectorbool 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;QueueInteger 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, QueueInteger 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] Trueflag Truefor i in range(index 1, len(arr)):if arr[index][i] 1:flag Falsedfs(arr, visited, i)if flag:global countcount 1count 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)
