n machines is given as an adjacency matrix network: network[i][j] == 1 when machines i and j are linked directly.
At the start, the machines listed in infected carry a virus. The virus travels along links: whenever one of two directly linked machines is infected, the other one gets infected too. This goes on until no one else can be infected.
Before the outbreak you may cure exactly one machine from infected. Note that the cured machine stays in the network and can catch the virus again from its neighbors.
Return the machine whose cure leads to the fewest infected machines in the end. If several choices tie, return the smallest index.network=[[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]], infected=[1, 2, 3] → 1
The network splits into two pairs, {0, 1} and {2, 3}. Curing 1 leaves nobody to infect 0, so only 2 machines end up infected. Curing 2 or 3 is useless: the other machine of that pair reinfects it, and all 4 end up infected.
network=[[1, 1, 1], [1, 1, 1], [1, 1, 1]], infected=[2, 0] → 0
All three machines are linked, so the whole network gets infected whatever we choose. On a tie we return the smaller index, 0.
network=[[1, 0, 0], [0, 1, 0], [0, 0, 1]], infected=[1] → 1
network is an n × n matrix of 0s and 1sinfected are distinctnetwork=[[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]], infected=[1, 2, 3]
1
Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.