Дима — системный администратор в университете. Сейчас он разбирается с крупной проблемой — некоторые из компьютеров в дисплейных классах дружественной университету школы заражены компьютерным вирусом. Антивирусное ПО не помогает — вирус слишком свежий...
Дима нашёл компьютер, с которого началось заражение, после чего собрал лог по всем переданным по локальной сети пакетам. Выяснилось, что в случае, если компьютер получил данные от компьютера, зараженного вирусом, компьютер заражается (при этом если компьютер только отправлял данные на зараженный компьютер, заражения не происходит).
Так как размер лога очень большой, Дима предлагает распараллелить усилия и просит Вас написать программу, которая определит список заражённых компьютеров (а сам он будет разбираться с тем, как обезвредить вирус на конкретном компьютере).
Формат ввода
Входные данные состоят из нескольких (не более 30) тестовых примеров.
Первая строка каждого тестового примера содержит два целых числа N и M (0 < N ≤ 2 ⋅ 104, 0 ≤ M ≤ 2 ⋅ 104), где N — количество компьютеров в школьной сети и M — количество записей в логе о переданных пакетах данных.
В последующих M строках задаются пакеты, по одному на строку. Каждый пакет задаётся тремя целыми числами ti, si и di — временем отправки пакета, номером компьютера, с которого был отправлен пакет и номером компьютера, на который был отправлен пакет, соответственно (0 ≤ ti ≤ 109, 1 ≤ si, di ≤ N, si ≠ di, все ti попарно различны).
Компьютер, зараженный первым, имеет id 1.
Входные данные завершаются строкой с двумя нулями. Обрабатывать эту строку как тестовый пример не требуется.
Гарантируется, что объём входных данных не превосходит 5 мебибайт.
Формат вывода
Для каждого тестового примера выведите одно число — количество компьютеров, заражённых вирусом.
Пример
Ввод
3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1
0 0
Вывод
3
1
Дима нашёл компьютер, с которого началось заражение, после чего собрал лог по всем переданным по локальной сети пакетам. Выяснилось, что в случае, если компьютер получил данные от компьютера, зараженного вирусом, компьютер заражается (при этом если компьютер только отправлял данные на зараженный компьютер, заражения не происходит).
Так как размер лога очень большой, Дима предлагает распараллелить усилия и просит Вас написать программу, которая определит список заражённых компьютеров (а сам он будет разбираться с тем, как обезвредить вирус на конкретном компьютере).
Формат ввода
Входные данные состоят из нескольких (не более 30) тестовых примеров.
Первая строка каждого тестового примера содержит два целых числа N и M (0 < N ≤ 2 ⋅ 104, 0 ≤ M ≤ 2 ⋅ 104), где N — количество компьютеров в школьной сети и M — количество записей в логе о переданных пакетах данных.
В последующих M строках задаются пакеты, по одному на строку. Каждый пакет задаётся тремя целыми числами ti, si и di — временем отправки пакета, номером компьютера, с которого был отправлен пакет и номером компьютера, на который был отправлен пакет, соответственно (0 ≤ ti ≤ 109, 1 ≤ si, di ≤ N, si ≠ di, все ti попарно различны).
Компьютер, зараженный первым, имеет id 1.
Входные данные завершаются строкой с двумя нулями. Обрабатывать эту строку как тестовый пример не требуется.
Гарантируется, что объём входных данных не превосходит 5 мебибайт.
Формат вывода
Для каждого тестового примера выведите одно число — количество компьютеров, заражённых вирусом.
Пример
Ввод
3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1
0 0
Вывод
3
1
Answers & Comments
Verified answer
Программа ни питоне 3, наивно реализующая то, что написано в задаче:
while True:
n, m = map(int, input().split())
if n == 0:
break
infected = set([1])
log = [[int(i) for i in input().split()] for _ in range(m)]
log.sort(key=lambda x: x[0])
for entry in log:
if entry[1] in infected:
infected.add(entry[2])
print(len(infected))
Считываем n и m, если это не нули, идем дальше. Считываем лог, на всякий случай сортируем его так, чтобы записи шли в хронологическом порядке. Создаем множество зараженных компьютеров, затем для каждой записи в логе проверяем, был ли отправитель заражен, если да - добавляем получателя в список зараженных. В конце выводим количество зараженных компьютеров.