题目描述
服务器连接方式包括直接连接和间接连接。
- 直接连接：若
matrix[i][j] == 1，则服务器i和j直接连接。 - 间接连接：若 A 和 B 直接连接，B 和 C 直接连接，则 A 和 C 间接连接。
- 广播规则：直接连接和间接连接都可以发送广播（即广播可以在连通分量内传播）。
给定一个 N \times N 的矩阵，代表 N 个服务器。
matrix[i][j] == 1：代表i和j直接连接。matrix[i][j] != 1（即为 0）：代表i和j不直接连接。matrix[i][i] == 1：自己和自己直接连接。matrix[i][j] == matrix[j][i]：连接是对称的。
目标：计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。
输入描述
- 输入为 N 行，每行有 N 个数字（0 或 1），由空格分隔，构成 N \times N 的数组。
- N 的范围为 1 \le N \le 40。
输出描述
- 输出一个数字，为需要广播的服务器的数量。
示例 1
输入
1 0 0
0 1 0
0 0 1
输出
3
说明
3 台服务器互不连接（除了自己连自己），形成 3 个独立的连通分量，所以需要分别向这 3 台服务器广播。
示例 2
输入
1 1
1 1
输出
1
说明
2 台服务器相互连接，属于同一个连通分量，所以只需要向其中一台服务器广播，另一台也能收到。
💡 解题思路与代码优化
原始代码分析
原始代码试图通过 Map 和 Set 来手动合并集合，逻辑比较复杂且存在潜在的错误。例如，在“取出间接相连的”循环中，直接修改 map 的值可能会导致引用混乱，且无法正确处理多跳（A-B-C-D）的情况，除非进行多次迭代或递归。
优化方案：连通分量（并查集或 DFS/BFS）
这个问题本质上是求无向图中连通分量的个数。
- 每个服务器是一个节点。
matrix[i][j] == 1表示节点i和j之间有一条边。- 我们需要找出图中有多少个独立的连通块。
方法一：深度优先搜索（DFS）
- 维护一个
visited数组，记录每个节点是否被访问过。 - 遍历所有节点，如果当前节点未被访问，说明发现了一个新的连通分量。
- 启动 DFS，将该连通分量内的所有节点标记为已访问。
- 连通分量计数加 1。
方法二：并查集（Union-Find）
- 初始化并查集，每个节点自成一个集合。
- 遍历矩阵，如果
matrix[i][j] == 1，则将i和j所在的集合合并。 - 最后统计并查集中有多少个独立的集合（根节点）。
这里采用 DFS 方法，因为它直观且代码简洁。
优化后的 Java 代码
import java.util.Scanner;
/**
* 题目：服务器广播
* 优化思路：计算无向图的连通分量个数 (使用 DFS)
*/
public class ServerBroadcastOptimized {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 1. 读取输入并构建矩阵
// 由于题目没有直接给出 N，我们需要先读取第一行来确定 N
if (!scanner.hasNextLine()) {
return;
}
String firstLine = scanner.nextLine().trim();
if (firstLine.isEmpty()) {
System.out.println(0);
return;
}
String[] firstRowStr = firstLine.split(" ");
int N = firstRowStr.length;
int[][] matrix = new int[N][N];
// 填充第一行
for (int i = 0; i < N; i++) {
matrix[0][i] = Integer.parseInt(firstRowStr[i]);
}
// 填充剩余行
for (int i = 1; i < N; i++) {
String[] rowStr = scanner.nextLine().trim().split(" ");
for (int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(rowStr[j]);
}
}
// 2. 使用 DFS 计算连通分量
boolean[] visited = new boolean[N];
int componentCount = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
// 发现一个新的连通分量
dfs(matrix, visited, i);
componentCount++;
}
}
System.out.println(componentCount);
}
/**
* 深度优先搜索，标记所有与 start 相连的节点
*/
private static void dfs(int[][] matrix, boolean[] visited, int start) {
visited[start] = true;
for (int i = 0; i < matrix.length; i++) {
// 如果 i 与 start 直接连接，且 i 未被访问过
if (matrix[start][i] == 1 && !visited[i]) {
dfs(matrix, visited, i);
}
}
}
}