专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
快递业务范围有 N 个站点，A 站点与 B 站点可以中转快递，则认为 A-B 站可达，如果 A-B 可达，B-C 可达，则 A-C 可达。
现在给 N 个站点编号 0、1、…n-1，用 s[i][j]表示 i-j 是否可达，s[i][j] = 1表示 i-j可达，s[i][j] = 0表示 i-j 不可达。
现用二维数组给定N个站点的可达关系，请计算至少选择从几个主站点出发，才能可达所有站点（覆盖所有站点业务）。
说明：s[i][j]与s[j][i]取值相同。
二、输入描述
第一行输入为 N，N表示站点个数。
之后 N 行表示站点之间的可达关系，第i行第j个数值表示编号为i和j之间是否可达。
1 < N < 10000。
三、输出描述
输出站点个数，表示至少需要多少个主站点。
示例：
1、输入：
4
1 1 1 1
1 1 1 0
1 1 1 0
1 0 0 1
2、输出：
1
3、说明：
选择 0 号站点作为主站点， 0 站点可达其他所有站点，所以至少选择 1 个站点作为主站才能覆盖所有站点业务。
四、解题思路
- 第一行输入站点个数N；
- 定义二维数组arrs，记录矩阵数据；
- 定义arrList，记录每一行的数字；
- 之后 N 行表示站点之间的可达关系；
- 将每一行的输入放入lineList集合；
- 遍历行数据arrList；
- 定义visitedSet，记录是否被访问过；
- 从 n 出发，访问 n 可达的所有快递点；
五、Java算法源码
package com.guor.od;
import java.util.*;
public class OdTest {
// 是否被访问过
private static Set<Integer> visitedSet = new HashSet<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 站点个数
int N = Integer.parseInt(sc.nextLine());
// 矩阵数据
int[][] arrs = new int[N][N];
// 每一行的数字集合
List<Integer>[] arrList = new List[N];
for (int i = 0; i < N; i++) {
String[] arr = sc.nextLine().split(" ");
List<Integer> lineList = new ArrayList<>();
int[] tmp = new int[N];
for (int j = 0; j < N; j++) {
tmp[j] = Integer.parseInt(arr[j]);
if (tmp[j] == 1 && i != j) {
lineList.add(j);
}
}
arrs[i] = tmp;
arrList[i] = lineList;
}
int cnt = 0;
for (int n = 0; n < arrList.length; n++) {
// 如果没有快递点可达，从这里再出发
if (!visitedSet.contains(n)) {
// 从 n 出发，访问 n 可达的所有快递点
dfs(arrList, n);
cnt++;
}
}
System.out.println(cnt);
}
// 从 n 出发，访问 n 可达的所有快递点
private static void dfs(List<Integer>[] nums, int n) {
// 已经被访问过
if (visitedSet.contains(n)) {
return;
}
// 该点已经访问
visitedSet.add(n);
for (Integer i : nums[n]) {
// 访问当前节点可达的邻节点
dfs(nums, i);
}
}
}
六、效果展示
1、输入
4
1 1 1 1
1 1 1 0
1 1 1 0
1 0 0 1
2、输出
1
3、说明
选择 0 号站点作为主站点， 0 站点可达其他所有站点，所以至少选择 1 个站点作为主站才能覆盖所有站点业务。
🏆下一篇：华为OD机试 - 荒岛求生 - 栈Stack（Java 2023 B卷 100分）
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。