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