题面简述

题目要求通过给定的确诊病例编号和接触矩阵，找出所有需要进行核酸检测的人员数量。需要检测的人是病毒传播链上的所有可能被传染的人，确诊病例无需再次检测。

解题思路

1. 模型化问题

   • 每个人作为一个节点，接触关系形成边，构成一个无向图。
   • 确诊病例是起点，从这些起点出发，利用广度优先搜索 (BFS) 遍历整个传播链。

2. 算法步骤

   1. 构建一个队列（queue）来保存当前待处理的传播链上的节点。
   2. 用一个集合（visited）保存已经访问过的节点，避免重复访问。
   3. 对每个确诊病例作为起点，将其接触的未访问节点加入队列。
   4. 遍历结束后，集合 visited 包含所有传播链上的节点，去除确诊病例，输出集合的大小。

3. 注意点

   • 确诊病例自身不算作需要检测的人。
   • 输入矩阵为对称矩阵，contact_matrix[i][j] = contact_matrix[j][i]。

复杂度分析

1. 时间复杂度
   • BFS 遍历每个节点最多一次，访问矩阵中所有接触关系：O(N^2)。
2. 空间复杂度
   • 队列和集合占用 O(N) 空间。

Python代码

from collections import deque

# 输入数据
N = int(input())  # 总人数
confirmed_cases = list(map(int, input().split(',')))  # 确诊病例编号

# 构建接触矩阵
contact_matrix = []
for _ in range(N):
    row = list(map(int, input().split(',')))
    contact_matrix.append(row)

# 需要核酸检测的集合
need_testing = set()

# 广度优先搜索(BFS)找出传播链条上的所有人员
queue = deque(confirmed_cases)
visited = set(confirmed_cases)  # 确诊病例已经访问过

while queue:
    current = queue.popleft()
    for i in range(N):
        # 如果有接触且尚未访问
        if contact_matrix[current][i] == 1 and i not in visited:
            need_testing.add(i)
            visited.add(i)
            queue.append(i)

# 输出需要核酸检测的总人数
print(len(need_testing))

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[] confirmedStr = sc.nextLine().split(",");
        List<Integer> confirmedCases = new ArrayList<>();
        for (String s : confirmedStr) {
            confirmedCases.add(Integer.parseInt(s));
        }
        int[][] contactMatrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] row = sc.nextLine().split(",");
            for (int j = 0; j < N; j++) {
                contactMatrix[i][j] = Integer.parseInt(row[j]);
            }
        }
        // 需要检测的集合
        Set<Integer> needTesting = new HashSet<>();
        // BFS队列
        Queue<Integer> queue = new LinkedList<>(confirmedCases);
        // 已访问的节点
        Set<Integer> visited = new HashSet<>(confirmedCases);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int i = 0; i < N; i++) {
                if (contactMatrix[current][i] == 1 && !visited.contains(i)) {
                    needTesting.add(i);
                    visited.add(i);
                    queue.offer(i);
                }
            }
        }
        System.out.println(needTesting.size());
    }
}

C++代码

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <sstream>
using namespace std;

int main() {
    int N;
    cin >> N; // 总人数
    cin.ignore();
    
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<int> confirmedCases;
    string num;
    while (getline(ss, num, ',')) {
        confirmedCases.push_back(stoi(num));
    }
    
    vector<vector<int>> contactMatrix(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            char c;
            cin >> c;
            contactMatrix[i][j] = c - '0';
            if (j < N - 1) cin.ignore(); // 跳过逗号
        }
    }
    
    set<int> needTesting;
    set<int> visited(confirmedCases.begin(), confirmedCases.end());
    queue<int> q;
    for (int caseNum : confirmedCases) {
        q.push(caseNum);
    }
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i < N; i++) {
            if (contactMatrix[current][i] == 1 && visited.find(i) == visited.end()) {
                needTesting.insert(i);
                visited.insert(i);
                q.push(i);
            }
        }
    }
    
    cout << needTesting.size() << endl;
    return 0;
}

题目内容

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

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

现在给定一组确诊人员编号（$X_1,X_2,X_3,...,X_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

输出

3

说明

编号为 $1、2$ 号的人员，为确诊病例。

$1$ 号和 $0$ 号有接触，$0$ 号和 $3$ 号有接触。

$2$ 号和 $4$ 号有接触。

所以，需要做核酸检测的人是 $0$ 号、$3$ 号、$4$ 号，总计 $3$ 人需要进行核酸检测。