#924
Minimize Malware Spread
master · 1670 · lc hard +32 · verified · 43% accepted · 1,117 likes · top 24%
Description
A network of n nodes is described by adjacency matrix graph (graph[i][j] == 1 means nodes i and j are connected). Nodes listed in initial start infected and spread malware to all reachable connected nodes. Remove exactly one node from initial to minimize the total number of eventually infected nodes. Return that node's index, choosing the smallest 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,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0
Example 3:
Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
Output: 1
Code
1
2
3