阅读量:2
题目
题目描述
服务器连接方式包括直接相连，间接连接。
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(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) 