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

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

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

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

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1090

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

🍏 LYA的生日聚会

问题描述

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

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

输入格式

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

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

接下来 $n$ 行，每行包含 $n$ 个用逗号隔开的数字，其中第 $i$ 行的第 $j$ 个数字表示编号为 $i$ 的人是否与编号为 $j$ 的人有过密切接触。数字为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<n<100$
• 人员编号从0开始

题解

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

参考代码

• Python

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

java">import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String[] s = sc.nextLine().split(",");
        Set<Integer> confirmed = new HashSet<>();
        for (String x : s) {
            confirmed.add(Integer.parseInt(x));
        }
        int[][] contact = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] line = sc.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                contact[i][j] = line[j].charAt(0) - '0';
            }
        }
        System.out.println(numToTest(n, confirmed, contact));
    }

    public static int numToTest(int n, Set<Integer> confirmed, int[][] contact) {
        Set<Integer> infected = new HashSet<>(confirmed);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (contact[i][j] == 1 || contact[j][i] == 1) {
                    if (infected.contains(i)) {
                        infected.add(j);
                    }
                    if (infected.contains(j)) {
                        infected.add(i);
                    }
                }
            }
        }
        return infected.size() - confirmed.size();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_set>
#include <sstream>

using namespace std;

int numToTest(int n, unordered_set<int>& confirmed, vector<vector<int>>& contact) {
    unordered_set<int> infected(confirmed);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (contact[i][j] == 1 || contact[j][i] == 1) {
                if (infected.count(i)) {
                    infected.insert(j);
                }
                if (infected.count(j)) {
                    infected.insert(i);
                }
            }
        }
    }
    return infected.size() - confirmed.size();
}

int main() {
    int n;
    cin >> n;
    cin.ignore();
    string s;
    getline(cin, s);
    unordered_set<int> confirmed;
    stringstream ss(s);
    string x;
    while (getline(ss, x, ',')) {
        confirmed.insert(stoi(x));
    }
    vector<vector<int>> contact(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        stringstream ss(s);
        for (int j = 0; j < n; j++) {
            getline(ss, x, ',');
            contact[i][j] = stoi(x);
        }
    }
    cout << numToTest(n, confirmed, contact) << endl;
    return 0;
}