Minimize Malware Spread

Given a graph and a list of initially infected nodes, remove one infected node so the final malware spread is minimized. DSU helps compute infected component sizes and decide which removal saves the most nodes.

Input Format

graph = adjacency matrix, initial = infected nodes

Output Format

node to remove

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

0

Explanation:

Removing either 0 or 1 saves the same number of nodes, so the smaller index 0 is chosen.

Example 2:

Input:

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

Output:

0

Explanation:

Each infected node is isolated; choose the smallest index.

Example 3:

Input:

graph = [[1,1,1],[1,1,1],[1,1,1]]
initial = [1,2]

Output:

1

Explanation:

Both infections affect the same component, so the smaller index is returned.

Loading...
Minimize Malware Spread - Union Find DSA Problem