网站开发平面设计师岗位要求,sogo提交网站入口,填空题ww秒懂2023,没有注册公司可以建网站吗题目 为了达到新冠疫情精准防控的需要#xff0c;为了避免全员核酸检测带来的浪费#xff0c;需要精准圈定可能被感染的人群。现在根据传染病流调以及大数据分析#xff0c;得到了每个人之间在时间、空间上是否存在轨迹的交叉。现在给定一组确诊人员编号 (X1, X2, X3, …, n…题目 为了达到新冠疫情精准防控的需要为了避免全员核酸检测带来的浪费需要精准圈定可能被感染的人群。现在根据传染病流调以及大数据分析得到了每个人之间在时间、空间上是否存在轨迹的交叉。现在给定一组确诊人员编号 (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;in;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(,);SetString set new HashSet();for(String s:arr){set.add(s);}// System.out.println(startListStr);StringTokenizer tokenizer new StringTokenizer(startListStr, ,);ListInteger 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 i0;in;i){for(int j0;jn;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(此时的countuf.count);}}}System.out.println(n- arr.length-uf.count1);}}
也可以使用BFS,DFS方法进行搜索 csdn
