最新华为OD机试真题-LYA的生日聚会(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

LYA的生日聚会(100分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🍏 LYA的生日聚会

问题描述

LYA要举办一个生日聚会，邀请了 位朋友参加。但是，由于最近流感病毒正在肆虐，LYA希望找出可能被感染的人群，以便及时采取防控措施。根据流行病学调查和大数据分析，得到了每个人之间是否有过密切接触的信息。现在已知一组确诊病例的编号 ，请你帮助LYA找出哪些人需要进行病毒检测，并输出需要检测的人数。注意，确诊病例本身不需要再做检测。

需要进行病毒检测的人，是指在病毒传播链条上的所有人员，即所有可能被确诊病例直接或间接传染的人。例如，如果A是确诊病例，A和B有过接触，B和C有过接触，C和D有过接触，那么B、C、D都需要进行病毒检测。

输入格式

第一行包含一个正整数 ，表示总人数。

第二行包含若干个用逗号隔开的正整数，表示确诊病例的编号。

接下来 行，每行包含 个用逗号隔开的数字，其中第 行的第 个数字表示编号为 的人是否与编号为 的人有过密切接触。数字为1表示有过接触，为0表示没有接触。

输出格式

输出一个整数，表示需要进行病毒检测的人数。

样例输入

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

样例输出

3

样例解释

在这个样例中，总共有5个人，编号分别为0到4。其中，编号为1和2的人是确诊病例。根据接触信息，我们可以发现：

• 编号为1的人和编号为0的人有过接触；
• 编号为0的人和编号为3的人有过接触；
• 编号为2的人和编号为4的人有过接触。

因此，编号为0、3、4的人都可能被感染，需要进行病毒检测。所以输出3，表示总共有3个人需要检测。

数据范围

• 
• 人员编号从0开始

题解

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来找出所有可能被感染的人。首先，将所有确诊病例加入到一个集合中，作为初始的感染者集合。然后，遍历每个人，如果这个人与任何一个已经在感染者集合中的人有过接触，就将其加入到感染者集合中。重复这个过程，直到感染者集合不再扩大为止。最后，感染者集合的大小减去初始确诊病例的数量，就是需要进行病毒检测的人数。

参考代码

• Python

n = int(input())
confirmed = set(map(int, input().split(',')))
contact = [list(map(int, input().split(','))) for _ in range(n)]

def num_to_test(n, confirmed, contact):
    infected = confirmed.copy()
    for i in range(n):
        for j in range(n):
            if contact[i][j] == 1 or contact[j][i] == 1:
                if i in infected:
                    infected.add(j)
                if j in infected:
                    infected.add(i)
    return len(infected) - len(confirmed)

print(num_to_test(n, confirmed, contact))

• Java

import java.util.*;

public class Main {
    public st