(C卷,100分)- 精准核酸检测（Java & JS & Python & C）

在线OJ刷题

题目描述

为了达到新冠疫情精准防控的需要，为了避免全员核酸检测带来的浪费，需要精准圈定可能被感染的人群。

现在根据传染病流调以及大数据分析，得到了每个人之间在时间、空间上是否存在轨迹交叉。

现在给定一组确诊人员编号（X1,X2,X3,…,Xn），在所有人当中，找出哪些人需要进行核酸检测，输出需要进行核酸检测的人数。（注意：确诊病例自身不需要再做核酸检测）

需要进行核酸检测的人，是病毒传播链条上的所有人员，即有可能通过确诊病例所能传播到的所有人。

例如：A是确诊病例，A和B有接触、B和C有接触、C和D有接触、D和E有接触，那么BCDE都是需要进行核酸检测的人。

输入描述

第一行为总人数 N

第二行为确认病例人员编号（确诊病例人员数量 < N），用逗号分割

第三行开始，为一个 N * N 的矩阵，表示每个人员之间是否有接触，0表示没有接触，1表示有接触。

输出描述

整数：需要做核酸检测的人数

备注

• 人员编号从0开始
• 0 < N < 100

用例

题目解析

本题可以用并查集解题。关于并查集的实现可以看：

华为校招机试 – 发广播（20210310）_华为机试 发广播 伏城之外-CSDN博客

即将有接触的人进行合并操作，纳入到同一个连通分量中。比如matrix[i]][j] == 1，即 i 和 j 就处于同一个连通分量中，需要进行合并。

另外，本题的接触关系矩阵matrix是沿对角线对称的，因此只需要遍历对角线一边即可。

当遍历完所有接触关系后，就可以求解每一个连通分量中的节点数，即每个接触群体的人数，求解原理如下：

并查集底层的fa数组，fa数组索引代表每个节点，fa数组元素代表对应索引的节点的根节点，而同一个连通分量中的节点的根都是相同的，因此，我们需要对fa每一个数组索引找一下根，这里可以使用并查集的find操作（递归实现），最后统计同一个根下的节点数量，即为同一个接触群体的人数。

当每个接触群体人数求解出来后，我们只需要统计”确诊病例人员编号“对应的根（连通分量）下的人数即可。

最后的统计的总人数需要减去确诊病例的数量，因为题目说：

确诊病例自身不需要再做核酸检测

本题需要注意的是，有可能多个确诊病人在同一个连通分量重，此时需要注意避免重复统计。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());
  const confirmed = (await readline()).split(",").map(Number);

  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(",").map(Number));
  }

  console.log(getResult(n, confirmed, matrix));
})();

class UnionFindSet {
  constructor(n) {
    this.fa = new Array(n).fill(true).map((_, idx) => idx);
  }

  // 查x站点对应的顶级祖先站点
  find(x) {
    while (x !== this.fa[x]) {
      x = this.fa[x];
    }
    return x;
  }

  // 合并两个站点，其实就是合并两个站点对应的顶级祖先节点
  union(x, y) {
    let x_fa = this.find(x);
    let y_fa = this.find(y);

    if (x_fa !== y_fa) {
      // 如果两个站点祖先相同，则在一条链上，不需要合并，否则需要合并
      this.fa[y_fa] = x_fa; // 合并站点，即让某条链的祖先指向另一条链的祖先
    }
  }
}

function getResult(n, confirmed, matrix) {
  const ufs = new UnionFindSet(n);

  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      if (matrix[i][j] == 1) {
        // 有过接触的人进行合并
        ufs.union(i, j);
      }
    }
  }

  // 统计每个接触群体（连通分量）中的人数
  const cnts = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    const fa = ufs.find(i);
    cnts[fa]++;
  }

  // 记录已统计过的感染群体
  const confirmed_fa = new Set();

  // 将有感染者的接触群体的人数统计出来
  let ans = 0;
  for (let i of confirmed) {
    const fa = ufs.find(i);

    // 已统计过的感染群体不再统计
    if (confirmed_fa.has(fa)) continue;
    confirmed_fa.add(fa);

    ans += cnts[fa];
  }

  // 最终需要做核酸的人数，不包括已感染的人
  return ans - confirmed.length;
}

Java算法源码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = Integer.parseInt(sc.nextLine());

    int[] confirmed = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();

    int[][] matrix = new int[n][n];
    for (int i = 0; i < n; i++) {
      matrix[i] = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    }

    System.out.println(getResult(n, confirmed, matrix));
  }

  public static int getResult(int n, int[] confirmed, int[][] matrix) {
    UnionFindSet ufs = new UnionFindSet(n);

    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        if (matrix[i][j] == 1) {
          // 有过接触的人进行合并
          ufs.union(i, j);
        }
      }
    }

    // 统计每个接触群体（连通分量）中的人数
    int[] cnts = new int[n];
    for (int i = 0; i < n; i++) {
      int fa = ufs.find(i);
      cnts[fa]++;
    }

    // 记录已统计过的感染群体
    HashSet<Integer> confirmed_fa = new HashSet<>();

    // 将有感染者的接触群体的人数统计出来
    int ans = 0;
    for (int i : confirmed) {
      int fa = ufs.find(i);

      // 如果该感染群体已统计过，则不再统计
      if (confirmed_fa.contains(fa)) continue;
      confirmed_fa.add(fa);

      ans += cnts[fa];
    }

    // 最终需要做核酸的人数，不包括已感染的人
    return ans - confirmed.length;
  }
}

// 并查集实现
class UnionFindSet {
  int[] fa;

  public UnionFindSet(int n) {
    this.fa = new int[n];
    for (int i = 0; i < n; i++) fa[i] = i;
  }

  public int find(int x) {
    if (x != this.fa[x]) {
      this.fa[x] = this.find(this.fa[x]);
      return this.fa[x];
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa = this.find(x);
    int y_fa = this.find(y);

    if (x_fa != y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Python算法源码

# 并查集实现
class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)

        if x_fa != y_fa:
            self.fa[y_fa] = x_fa


# 输入获取
n = int(input())
confirmed = list(map(int, input().split(",")))
matrix = [list(map(int, input().split(","))) for _ in range(n)]


# 算法入口
def getResult():
    ufs = UnionFindSet(n)

    for i in range(n):
        for j in range(i, n):
            if matrix[i][j] == 1:
                # 有过接触的人进行合并
                ufs.union(i, j)

    # 统计每个接触群体（连通分量）中的人数
    cnts = [0] * n
    for i in range(n):
        fa = ufs.find(i)
        cnts[fa] += 1

    # 记录已统计过的可能感染群体
    confirmed_fa = set()

    # 将有感染者的接触群体的人数统计出来
    ans = 0
    for i in confirmed:
        fa = ufs.find(i)

        # 已统计过的可能感染群体不再统计
        if fa in confirmed_fa:
            continue
        confirmed_fa.add(fa)

        ans += cnts[fa]

    # 最终需要做核酸的人数，不包括已感染的人
    return ans - len(confirmed)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

/** 并查集定义 **/
typedef struct {
    int *fa;
} UFS;

UFS *new_UFS(int n) {
    UFS *ufs = (UFS *) malloc(sizeof(UFS));

    ufs->fa = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        ufs->fa[i] = i;
    }

    return ufs;
}

int find_UFS(UFS *ufs, int x) {
    if (x != ufs->fa[x]) {
        ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);
        return ufs->fa[x];
    }
    return x;
}

void union_UFS(UFS *ufs, int x, int y) {
    int x_fa = find_UFS(ufs, x);
    int y_fa = find_UFS(ufs, y);

    if (x_fa != y_fa) {
        ufs->fa[y_fa] = x_fa;
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int confirmed[MAX_SIZE];
    int confirmed_size = 0;

    while (scanf("%d", &confirmed[confirmed_size++])) {
        if (getchar() != ',') break;
    }

    UFS *ufs = new_UFS(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int v;
            scanf("%d", &v);

            // 有过接触的人进行合并
            if (v == 1) {
                union_UFS(ufs, i, j);
            }

            getchar();
        }
    }

    // 统计每个接触群体（连通分量）中的人数
    int cnts[MAX_SIZE] = {0};
    for (int i = 0; i < n; i++) {
        int fa = find_UFS(ufs, i);
        cnts[fa]++;
    }

    // 记录已统计过的可能感染群体
    int confirmed_fa[MAX_SIZE] = {0};

    // 将有感染者的接触群体的人数统计出来
    int ans = 0;
    for (int i = 0; i < confirmed_size; i++) {
        int fa = find_UFS(ufs, confirmed[i]);

        // 已统计过的可能感染群体不再统计
        if(confirmed_fa[fa]) continue;
        confirmed_fa[fa] = 1;

        ans += cnts[fa];
    }

    // 最终需要做核酸的人数，不包括已感染的人
    printf("%dn", ans - confirmed_size);

    return 0;
}