#928
Minimize Malware Spread II
candidate master · 1560 · lc hard +32 · verified · 45.5% accepted · 708 likes · top 29%
Description
A network is described by adjacency matrix graph. Nodes in initial start infected and spread malware to all connected nodes. Unlike the first variant, removing a node from initial here means physically deleting that node and all its edges from the graph. Remove exactly one such node to minimize the total infected count. Return the smallest index in case of a tie.
Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1
Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1
Code
1
2
3