Minimize Malware Spread in a Facility Network
Problem statement
An undirected facility network is represented by an adjacency matrix graph. Every center in initial is compromised, and compromise spreads through connected centers.
Remove exactly one center from the initial compromised set before spread begins. Return the center whose removal minimizes the final number of compromised centers. If several choices are equally good, return the smallest center ID.
Function
minMalwareSpread(graph: int[][], initial: int[]) → intExamples
Example 1
graph = [[1,1,0],[1,1,0],[0,0,1]]initial = [0,1]return = 0Removing either 0 or 1 leaves the same connected component infected, so the smaller ID wins.
Example 2
graph = [[1,0,0],[0,1,0],[0,0,1]]initial = [0,2]return = 0Either removal saves one isolated center, so return 0.
Example 3
graph = [[1,1,1],[1,1,1],[1,1,1]]initial = [1,2]return = 1One infection remains in the shared component, making the smaller candidate the tie-break winner.
Constraints
1 ≤ graph.length ≤ 300andgraphis square.graph[i][j]is0or1, symmetric, andgraph[i][i] = 1.initialis non-empty and contains distinct valid center IDs.