华为OD机试统一考试-精准核酸检测

题目描述

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

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

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

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

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

输入描述

第一行为总人数 N

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

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

输出描述

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

备注

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

用例

题目解析

本题可以用并查集解题。

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

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

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

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

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

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

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

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

public func ODTest_6() {
    print("第一行为总人数N")
    let N = Int(readLine() ?? "") ?? 0
    var matrix: [[Int]] = []
    print("第二行为确诊病例人员编号 (确证病例人员数量 < N) ，用逗号隔开")
    let confirmedSet = readLine()?.split(separator: ",").map { Int($0) ?? 0 } ?? []
    print("接下来N行，每一行有N个数字，用逗号隔开，其中第i行的第个j数字表名编号