Minimize Malware Spread

Statement

You’re given a network of $n$ nodes as an $n \times n$ adjacency matrix graph with the $i^{th}$ node directly connected to the $j^{th}$ node if graph[i][j] == 1.

A list of nodes, initial, is given, which contains nodes initially infected by malware. When two nodes are connected directly and at least one of them is infected by malware, both nodes will be infected by malware. This spread of malware will continue until every node in the connected component of nodes has been infected.

After the infection has stopped spreading, $M$ will represent the final number of nodes in the entire network that have been infected with malware.

Return a node from initial such that, when this node is removed from the graph, $M$ is minimized. If multiple nodes can be removed to minimize $M$, return the node with the smallest index.

Note: If a node was removed from the initial list of infected nodes, it might still be infected later on due to the malware’s spread.

Constraints:

• graph.length == graph[i].length
• $2 \leq$ n $\leq 50$
• graph[i][j] is $0$ or $1$.
• graph[i][j] == graph[j][i]
• graph[i][i] == 1
• $1 \leq$ initial.length $\leq n$
• $0 \leq$ initial[i] $\leq n - 1$
• All the integers in the initial are unique.

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself

Implement your solution in MinimizeMalware.java in the following coding playground. You will need the provided supporting code to implement your solution.