服务器广播

题目

服务器连接方式包括直接相连，间接连接。
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); } } } }