笔试时间：2023年9月18日 秋招

第一题

题目

假设有一种可以在人与人之间进行快速传播的新型病毒 (记为V)，如果有人(记为A)感染了这种病毒，并在某个时刻t和另一个人 B 接触，那么B 也会立刻感染病毒 V。现有如下条件:

1、给定一个正整数n，代表n 个人，这些人的编号从0到n-1；

2、给定一个下标从0开始的二维数组 meetings，其中 meetings[i]=[xi,yi,ti] 表示人员xi和yi在时刻ti有过接触；在 meetings 代表的所有接触发生期间，感染者会一直处于感染状态；

3、同一个人A可以在某一时刻同时和多个人接触，且如果A感染了病毒V，那么和A接触的所有人都会立刻感染该病毒；即：假设人员xi和yi在时刻ti有过接触，如果 xi 感染了病毒 V，那么yi 也会感染该病毒，反之亦然；

4、病毒V的感染是瞬间发生的，也就是说，如果人员A在时刻t 感染了病毒，那么A马上就可以把病毒V 传染给接触到的其他人；

5、给定一个整数 firstPerson，代表某个人，且 0 < firstPerson< n；

6、人员 0 感染了病毒V，并在时刻 0与 firstPerson 有过接触。

在meetings代表的所有接触都发生之后，请返回感染病毒V的所有感染者的编号列表，并按照从小到大的顺序记录人员编号。

样例输入

6,[[1 2,5][2 3 8],[1 5 101],1

样例输出

[0,1,2,3,5]

说明

时刻0，人员0与人员1接触，人员1 感染病毒

时刻5，人员1与人员2 接触，人员2 感染病毒

时刻8，人员2与人员3 接触，人员3 感染病毒,

时刻 10，人员1与人员 5接触，人员5感染病毒。

因此，在所有接触发生后，人员0、1、2、3、5都是感染者。

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

class Spread {
public:
    int p1;
    int p2;
    int time;

    Spread(int p1, int p2, int time) : p1(p1), p2(p2), time(time) {}

    int getP1() const {
        return p1;
    }

    int getP2() const {
        return p2;
    }

    int getTime() const {
        return time;
    }
};

std::vector<int> findAllPerson(int n, std::vector<std::vector<int>>& meetings, int firstPerson) {
    std::vector<Spread> list;
    std::set<int> set;
    int len = meetings.size();

    // 添加传播事件到列表
    for (int i = 0; i < len; i++) {
        int p1 = meetings[i][0];
        int p2 = meetings[i][1];
        int time = meetings[i][2];
        list.push_back(Spread(p1, p2, time));
    }

    // 第0号人进行传播给firstPerson
    set.insert(0);
    set.insert(firstPerson);

    // 按时间进行排序
    std::sort(list.begin(), list.end(), [](const Spread& o1, const Spread& o2) {
        return o1.getTime() < o2.getTime();
    });

    // 判断传播途径
    for (const Spread& spread : list) {
        if (set.count(spread.getP1()) || set.count(spread.getP2())) {
            // 都被感染
            set.insert(spread.getP1());
            set.insert(spread.getP2());
        }
    }

    // 转为vector并排序
    std::vector<int> ans(set.begin(), set.end());
    std::sort(ans.begin(), ans.end());

    return ans;
}

// test-提交时不需要
int main() {
    int n = 6;
    std::vector<std::vector<int>> meetings = {{1, 2, 5}, {2, 3, 8}, {1, 5, 101}};
    int firstPerson = 1;
    std::vector<int> result = findAllPerson(n, meetings, firstPerson);

    for (int person : result) {
        std::cout << person << " ";
    }
    std::cout << std::endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

class SpreadSimulator {
    public ArrayList<Integer> findAllPerson(int n, int[][] meetings, int firstPerson) {
        List<Spread> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>(); //进行去重
        int len = meetings.length; //有几条Spread

        // 添加传播事件到列表
        for (int i = 0; i < len; i++) {
            int p1 = meetings[i][0];
            int p2 = meetings[i][1];
            int time = meetings[i][2];
            list.add(new Spread(p1, p2, time));
        }

        // 第0号人进行传播给firstPerson
        set.add(0);
        set.add(firstPerson);

        // 按时间进行排序
        Collections.sort(list, new Comparator<Spread>() {
            @Override
            public int compare(Spread o1, Spread o2) {
                return o1.getTime() - o2.getTime();
            }
        });

        // 判断传播途径
        for (Spread spread : list) {
            if (set.contains(spread.getP1()) || set.contains(spread.getP2())) {
                // 都被感染
                set.add(spread.getP1());
                set.add(spread.getP2());
            }
        }

        // 转为list
        ArrayList<Integer> ans = new ArrayList<>(set);

        // 排序
        Collections.sort(ans);

        return ans;
    }

/