华为机试题-核酸检测人数

题目

为了达到新冠疫情精准防控的需要，为了避免全员核酸检测带来的浪费，需要精准圈定可能被感染的人群。现在根据传染病流调以及大数据分析，得到了每个人之间在时间、空间上是否存在轨迹的交叉。现在给定一组确诊人员编号 (X1, X2, X3, …, n)，在所有人当中，找出哪些人需要进行核酸检测，输出需要进行核酸检测的人数。(注意：确诊病例自身不需要再做核酸检测)
需要进行核酸检测的人，是病毒传播链条上的所有人员，即有可能通过确诊病例所能传播到的所有人。
例如：A是确诊病例，A和B有接触、B和C有接触、C和D有接触、D和E有接触，那么B\C\D\E都是需要进行核酸检测的人。
输入描述
第一行为总人数N
第二行为确诊病例人员编号(确诊病例人员数量<N)，用逗号分割
第三行开始，为一个N*N的矩阵，表示每个人员之间是否有接触，0表示没有接触，1表示有接触。
输出描述
整数：需要做核酸检测的人数
补充说明
人员编号从0开始
0 < N < 100
1
示例
输入
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
1
2
3
4
5
6
7
输出
3
1
补充说明
编号为1、2号的人员，为确诊病例。1号和0号有接触，0号和3号有接触。
2号和4号有接触。所以，需要做核酸检测的人是0号、3号、4号，总计3人需要进行核酸检测

参考代码

方法：并查集

package RealTest;
import java.util.*;/*** @ClassName nucleicAcidNumber* @Description TODO* @Author 21916* @Date 2024/3/27 14:58*/class UF{int count;int[] parent;public UF(int n){this.count = n;parent = new int[n];for(int i =0;i<n;i++){parent[i]  =i;}}public void union(int p,int q){if(find(p)==find(q)) return;parent[p] = q;this.count--;}public int find(int x){if(x!=parent[x]){parent[x]  = find(parent[x]);}return parent[x];}}
public class nucleicAcidNumber {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.nextLine(); // Consume newlineString startListStr = scanner.nextLine();String[] arr = startListStr.split(",");Set<String> set = new HashSet<>();for(String s:arr){set.add(s);}// System.out.println(startListStr);StringTokenizer tokenizer = new StringTokenizer(startListStr, ",");List<Integer> startList = new ArrayList<>();while (tokenizer.hasMoreTokens()) {startList.add(Integer.parseInt(tokenizer.nextToken()));}int[][] mat = new int[n][n];for (int i = 0; i < n; i++) {String row = scanner.nextLine();tokenizer = new StringTokenizer(row, ",");for (int j = 0; j < n; j++) {mat[i][j] = Integer.parseInt(tokenizer.nextToken());}}UF uf = new UF(n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(mat[i][j]==1&&(set.contains(i+"")|| set.contains(j+""))){uf.union(i,j);set.add(i+"");set.add(j+"");// System.out.println("此时的count"+uf.count);}}}System.out.println(n- arr.length-uf.count+1);}}

也可以使用BFS,DFS方法进行搜索
csdn