Tap here to switch tabs
Problem
Submissions

Problem: Minimize Malware Spread

Minimize Malware Spread gives a graph and initially infected nodes. Choose one listed node to remove, even if it may be reinfected, minimizing final infections and using the smallest index on ties.

Statement

You’re given a network of nn nodes as an n×nn \times n adjacency matrix graph with the ithi^{th} node directly connected to the jthj^{th} node if graph[i][j] == 1.

A list of nodes, initial, is given, which contains nodes initially infected by malware. When two nodes are connected directly and at least one of them is infected by malware, both nodes will be infected by malware. This spread of malware will continue until every node in the connected component of nodes has been infected.

After the infection has stopped spreading, MM will represent the final number of nodes in the entire network that have been infected with malware.

Return a node from initial such that, when this node is removed from the graph, MM is minimized. If multiple nodes can be removed to minimize MM, return the node with the smallest index.

Note: If a node was removed from the initial list of infected nodes, it might still be infected later on due to the malware’s spread.

Constraints:

  • graph.length == graph[i].length
  • 2≤2 \leq n ≤50\leq 50
  • graph[i][j] is 00 or 11.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1≤1 \leq initial.length ≤n\leq n
  • 0≤0 \leq initial[i] ≤n−1\leq n - 1
  • All the integers in the initial are unique.
⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimize Malware Spread

Minimize Malware Spread gives a graph and initially infected nodes. Choose one listed node to remove, even if it may be reinfected, minimizing final infections and using the smallest index on ties.

Statement

You’re given a network of nn nodes as an n×nn \times n adjacency matrix graph with the ithi^{th} node directly connected to the jthj^{th} node if graph[i][j] == 1.

A list of nodes, initial, is given, which contains nodes initially infected by malware. When two nodes are connected directly and at least one of them is infected by malware, both nodes will be infected by malware. This spread of malware will continue until every node in the connected component of nodes has been infected.

After the infection has stopped spreading, MM will represent the final number of nodes in the entire network that have been infected with malware.

Return a node from initial such that, when this node is removed from the graph, MM is minimized. If multiple nodes can be removed to minimize MM, return the node with the smallest index.

Note: If a node was removed from the initial list of infected nodes, it might still be infected later on due to the malware’s spread.

Constraints:

  • graph.length == graph[i].length
  • 2≤2 \leq n ≤50\leq 50
  • graph[i][j] is 00 or 11.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1≤1 \leq initial.length ≤n\leq n
  • 0≤0 \leq initial[i] ≤n−1\leq n - 1
  • All the integers in the initial are unique.