n компьютеров задана матрицей смежности network: network[i][j] == 1, если компьютеры i и j соединены напрямую.
В начале заражены компьютеры из списка infected. Вирус распространяется по связям: если один из двух напрямую соединённых компьютеров заражён, заражается и второй. Так продолжается, пока заражать больше некого.
До начала эпидемии можно вылечить ровно один компьютер из infected. Учтите, что вылеченный компьютер остаётся в сети и может заразиться снова от соседей.
Верните номер компьютера, после лечения которого в итоге заразится как можно меньше компьютеров. Если вариантов несколько, верните наименьший номер.network=[[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]], infected=[1, 2, 3] → 1
Сеть распадается на две пары: {0, 1} и {2, 3}. Если вылечить 1, вирусу некому будет заразить 0, и итог — 2 заражённых. Вылечить 2 или 3 бесполезно: второй компьютер этой пары снова их заразит, итог — 4.
network=[[1, 1, 1], [1, 1, 1], [1, 1, 1]], infected=[2, 0] → 0
Все три компьютера связаны, так что при любом выборе заразится вся сеть. При равенстве возвращаем меньший номер — 0.
network=[[1, 0, 0], [0, 1, 0], [0, 0, 1]], infected=[1] → 1
network — матрица n × n из 0 и 1infected различныnetwork=[[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]], infected=[1, 2, 3]
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 72 теста на сервере, включая скрытые.