Show problems as
Classic problem #924HardArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Minimize Malware Spread

Real-world version: Which Faulty Unit to Take Offline
Tracked in this browser only
Read Minimize Malware Spread on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rack of units is given as graph, where graph[i][j] is 1 when units i and j are wired together. Every unit is wired to itself, and the wiring runs both ways.

The units listed in initial start out faulty. A fault spreads along the wiring until every unit reachable from a faulty one is faulty too.

Exactly one unit is taken off the fault list before anything spreads; it stays in the rack and still carries the fault onward if something reaches it. Choose the one that leaves the fewest units faulty at the end, and return it. When two choices leave the same number faulty, return the smaller unit number.

Examples

Example 1

Input
graph = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]], initial = [1, 2]
Output
2

Unit 1 sits alone with unit 0 in a group of two, and unit 2 sits in a group of three. Each group holds one faulty unit, so taking off unit 2 saves three while taking off unit 1 saves only two.

Example 2

Input
graph = [[1, 1], [1, 1]], initial = [0, 1]
Output
0

Both units are wired together and both are faulty, so whichever is taken off the list the other still fills the group. The tie falls to the smaller number.

Example 3

Input
graph = [[1, 0, 0], [0, 1, 0], [0, 0, 1]], initial = [0, 1, 2]
Output
0

No unit is wired to any other, so taking one off the list saves exactly that one, and all three choices are equal.

Constraints

  • 2 <= graph.length <= 300
  • graph.length == graph[i].length
  • graph[i][j] is 0 or 1
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length <= graph.length
  • 0 <= initial[i] <= graph.length - 1
  • The unit numbers in initial are all different

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_malware_spread(graph: list[list[int]], initial: list[int]) -> int:
Java
public int minMalwareSpread(int[][] graph, int[] initial)

More on the same topics