ICPC国内予選2020 B問題：接触追跡

問題. 接触追跡

あるアプリを利用している人が 人いる。その中で 番目の利用者は感染者である。時刻順に濃厚接触の記録が 件与えられる。 番目の記録 は 番目と 番目の利用者が濃厚接触したことを表している。感染者と直接的または間接的に感染した疑いのある利用者の総数を求めよ。

制約： 、

解法．

初めに 番目の利用者は感染している。時刻順に 番目の利用者が濃厚接触したときを考える。お互いがその時点で感染していなければ濃厚接触しても感染者とはならない。ただし、二人のうち少なくとも一人が感染していると他方も感染者となる。一度、感染者になると今後もずっと感染者なので、感染者になったかどうかの配列を用意して時系列順に記録していけば感染者の総数が求まる。

計算時間：

ソースコードを表示

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

using namespace std;

int main() {
    int m, n, p;
    while (cin >> m >> n >> p, m) {
        vector<bool> infect(m + 1, false);
        infect[p] = true;
        for (int i = 0, a, b; i < n; ++i) {
            cin >> a >> b;
            infect[a] = infect[b] = infect[a] or infect[b];
        }
        cout << std::count(infect.begin(), infect.end(), true) << std::endl;
    }

    return 0;
}

　

時事問題。