Description
You are given a network of n nodes represented as an n x n adjacency matrix graph. Some nodes initial are initially infected by malware. Return the node that, if removed, would minimize the final number of nodes infected.
Examples
Input:
graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]Output:
0Explanation:
Remove node 0 to minimize spread.
Input:
graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0, 1]Output:
0Explanation:
Edge case returning zero.
Input:
graph = [[1,1,1,0],[1,1,0,0],[1,0,1,1],[0,0,1,1]], initial = [0,3]Output:
3Explanation:
The network has two connected components: {0,1,2} and {2,3}. Node 2 bridges both components. Node 0 infects {0,1,2} and node 3 infects {2,3}, so all 4 nodes get infected regardless. Removing node 0 from the initial list still leaves node 2 infected via node 3, so all nodes remain infected. The answer is 0 (smallest index).
Constraints
- •
n == graph.length - •
n == graph[i].length - •
2 ≤ n ≤ 300