服务器广播

题目服务器连接方式包括直接相连间接连接。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] 。计算初始需要给几台服务器广播才可以使侮个服务器都收到广播。思路有几个连通块就需要几次广播代码import java.util.*; public class Main { public static void main(String[] args) { int[][] matrix { {1, 1, 0}, {1, 1, 0}, {0, 0, 1} }; System.out.println(countBroadcast(matrix)); // 输出 2 } public static int countBroadcast(int[][] matrix) { int n matrix.length; boolean[] visited new boolean[n]; int count 0; for (int i 0; i n; i) { if (!visited[i]) { // 每发现一个新连通块需要一次广播 count; dfs(matrix, i, visited); } } return count; } // 深度优先遍历把整个连通块标为已访问 private static void dfs(int[][] matrix, int i, boolean[] visited) { visited[i] true; for (int j 0; j matrix.length; j) { // i 和 j 直接相连 j 没被访问 if (matrix[i][j] 1 !visited[j]) { dfs(matrix, j, visited); } } } }