返回目录

题目描述

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

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

现在给定一组确诊人员编号 (X1,X2,X3,…Xn)在所有人当中，找出哪些人需要进行核酸检测，输出需要进行核酸检测的数。

(注意:确诊病例自身不需要再做核酸检测)需要进行核酸检测的人，是病毒传播链条上的所有人员，即有可能通过确诊病例所能传播到的所有人。

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

输入描述

第一行为总人数N

第二行为确证病例人员编号（确证病例人员数量<N），用逗号隔开

接下来N行，每一行有N个数字，用逗号隔开，其中第i行的第j个数字表名编号i是否与编号j接触过。0表示没有接触，1表示有接触

备注：

人员编号从0开始

0 < N < 100 0<N<1000<N<100

输出描述

输出需要做核酸检测的人数

示例：

解题思路

1. 初始化一个大小为N的布尔数组 visited，用来记录每个人是否已经被访问过（即是否已经确定需要进行核酸检测）。
2. 初始化一个大小为N×N的布尔矩阵 contacts，用来表示人与人之间的接触情况。如果 contacts[i][j]为 true，则表示编号为i的人与编号为j的人有接触。

3. 从输入中读取确诊病例的编号，并对每个确诊病例执行深度优先搜索（DFS）：

   • 在DFS中，首先将当前节点（即当前人员编号）标记为已访问。
   • 然后遍历该节点的所有邻接节点（即与当前人员有接触的所有人），如果邻接节点未被访问，则递归地对邻接节点执行DFS。
4. 完成DFS后，遍历 visited数组，统计除确诊病例外的已访问节点的数量，即为需要进行核酸检测的人数。

用例模拟计算过程：

1. 初始化 visited数组为 [false, false, false, false, false]。

2. 构建 contacts矩阵如下：

   [true,  true,  false, true,  false]
   [true,  true,  false, false, false]
   [false, false, true,  false, true ]
   [true,  false, false, true,  false]
   [false, false, true,  false, true ]

3. 对于确诊病例1和2，执行DFS：

   • DFS(1): 标记 visited[1]为 true，检查与1有接触的人，发现0和3，递归DFS(0)和DFS(3)。

     • DFS(0): 标记 visited[0]为 true，检查与0有接触的人，发现3，但3已在DFS(1)中被访问，所以不再递归。
     • DFS(3): 标记 visited[3]为 true，检查与3有接触的人，发现0，但0已在DFS(0)中被访问，所以不再递归。

   • DFS(2): 标记 visited[2]为 true，检查与2有接触的人，发现4，递归DFS(4)。

     • DFS(4): 标记 visited[4]为 true，检查与4有接触的人，发现2，但2已在DFS(2)中被访问，所以不再递归。
4. DFS执行完毕后，visited数组为 [true, true, true, true, true]。
5. 统计除确诊病例外的已访问节点数量，即 visited中为 true的元素数量减去确诊病例的数量。在这个用例中，所有人都被访问过，但需要排除确诊病例1和2，所以需要进行核酸检测的人数为5 - 2 = 3。

Python算法源码

def dfs(contacts, visited, start):
    visited[start] = True  # 标记当前节点为已访问
    for i, has_contact in enumerate(contacts[start]):
        if has_contact and not visited[i]:
            dfs(contacts, visited, i)  # 递归访问该节点

def main():
    N = int(input())  # 读取人数
    confirmed_cases = set(map(int, input().split(',')))  # 读取确诊病例人员编号

    contacts = []
    for _ in range(N):
        line = input().split(',')  # 读取每行接触矩阵数据
        contacts.append([contact == "1" for contact in line])

    visited = [False] * N  # 访问记录

    # 对每个确诊病例执行深度优先搜索
    for index in confirmed_cases:
        if not visited[index]:
            dfs(contacts, visited, index)

    count = sum(1 for i, v in enumerate(visited) if v and i not in confirmed_cases)
    print(count)  # 输出需要进行核酸检测的人数

if __name__ == "__main__":
    main()

C算法源码

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

// 深度优先搜索（DFS）算法
void dfs(const int** contacts, int* visited, int start, int N) {
    visited[start] = 1; // 标记当前节点为已访问
    for (int i = 0; i < N; ++i) {
        // 如果当前节点与其他节点有接触，并且该节点未被访问过
        if (contacts[start][i] && !visited[i]) {
            dfs(contacts, visited, i, N); // 递归访问该节点
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);
    getchar(); // 忽略换行符

    char line[1000];
    fgets(line, 1000, stdin);
    char* token = strtok(line, ",");
    int confirmedCases[1000] = {0};
    int confirmedCount = 0;

    // 读取确诊病例人员编号
    while (token != NULL) {
        confirmedCases[confirmedCount++] = atoi(token);
        token = strtok(NULL, ",");
    }

    int** contacts = (int**)malloc(N * sizeof(int*));
    for (int i = 0; i < N; ++i) {
        contacts[i] = (int*)malloc(N * sizeof(int));
    }
    int* visited = (int*)calloc(N, sizeof(int));

    // 构建接触矩阵
    for (int i = 0; i < N; ++i) {
        fgets(line, 1000, stdin);
        token = strtok(line, ",");
        int j = 0;
        while (token != NULL) {
            contacts[i][j++] = atoi(token);
            token = strtok(NULL, ",");
        }
    }

    // 对每个确诊病例执行深度优先搜索
    for (int i = 0; i < confirmedCount; ++i) {
        if (!visited[confirmedCases[i]]) {
            dfs((const int**)contacts, visited, confirmedCases[i], N);
        }
    }

    int count = 0; // 需要进行核酸检测的人数
    // 遍历访问记录数组，统计需要进行核酸检测的人数
    for (int i = 0; i < N; ++i) {
        if (visited[i] && !confirmedCases[i]) {
            count++; // 如果该人员被访问过且不是确诊病例，则计数器加一
        }
    }

    printf("%d\n", count); // 输出需要进行核酸检测的人数

    // 释放分配的内存
    free(visited);
    for (int i = 0; i < N; ++i) {
        free(contacts[i]);
    }
    free(contacts);

    return 0;
}

java算法源码

import java.util.*;

public class Main {

    // 深度优先搜索（DFS）算法
    static void dfs(boolean[][] contacts, boolean[] visited, int start) {
        visited[start] = true; // 标记当前节点为已访问
        for (int i = 0; i < contacts.length; ++i) {
            // 如果当前节点与其他节点有接触，并且该节点未被访问过
            if (contacts[start][i] && !visited[i]) {
                dfs(contacts, visited, i); // 递归访问该节点
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine(); // 忽略换行符

        String line = scanner.nextLine();
        String[] caseIndices = line.split(",");
        Set<Integer> confirmedCases = new HashSet<>();

        // 读取确诊病例人员编号
        for (String caseIndex : caseIndices) {
            confirmedCases.add(Integer.parseInt(caseIndex));
        }

        boolean[][] contacts = new boolean[N][N];
        boolean[] visited = new boolean[N];

        // 构建接触矩阵
        for (int i = 0; i < N; ++i) {
            line = scanner.nextLine();
            String[] contactsRow = line.split(",");
            int j = 0;
            for (String contact : contactsRow) {
                contacts[i][j++] = contact.equals("1");
            }
        }

        // 对每个确诊病例执行深度优先搜索
        for (int index : confirmedCases) {
            if (!visited[index]) {
                dfs(contacts, visited, index);
            }
        }

        int count = 0; // 需要进行核酸检测的人数
        // 遍历访问记录数组，统计需要进行核酸检测的人数
        for (int i = 0; i < N; ++i) {
            if (visited[i] && !confirmedCases.contains(i)) {
                count++; // 如果该人员被访问过且不是确诊病例，则计数器加一
            }
        }

        System.out.println(count); // 输出需要进行核酸检测的人数
    }
}