FastPrep

Description

Solutions

Malware Spread

🔥 FULLTIME📚RELATED PROBLEMS

Implement a prototype service for malware spread control in a network.

There are g_nodes servers in a network and g_edges connections between its nodes. The bi-directional connection connects g_from[i] and g_to[i]. Some of the nodes are infected with malware. They are listed in a binary array, where if malware[i] = 1 node i is infected, and if malware[i] = 0, node i is not infected.

Any infected node infects other non-infected nodes, which are directly connected. This process goes on until no new infections are possible. Exactly 1 node can be removed from the network. Return the index of the node to remove such that the total infected nodes in the remaining network are minimized. If multiple nodes lead to the same minimum result, then return the one with the lowest index.

Function Description

Complete the function getNodeToRemove in the editor.

getNodeToRemove has the following parameter(s):

int g_nodes: the number of nodes
int g_from[n]: one end of the connections
int g_to[n]: the other end of the connections
int malware[n]: the affected nodes

Returns

int: the optimal node to remove

Example 1:

Input:  g_nodes = 9, g_from = [1, 2, 4, 6, 7], g_to = [2, 3, 5, 7, 8], malware = [0, 0, 1, 0, 1, 0, 0, 0, 0]
Output: 3 
Explanation:
Initially, nodes [3, 5] are infected. At the end, nodes [1, 2, 3, 4, 5] will be infected. If node 3 is removed, only nodes 4 and 5 are infected, which is the minimum possible. Return 3, the node to remove.

Example 2:

Input:  g_nodes = 5, g_from = [1, 2, 3, 4], g_to = [2, 3, 4, 5], malware = [1, 1, 1, 1, 1]
Output: 1 
Explanation:
All nodes are infected even after removing any node. Return the lowest index, 1, as the answer.

Constraints:

1 ≤ g_nodes ≤ 10^3

0 ≤ g_edges ≤ min(g_nodes*(g_nodes-1)/2, 10^3)

1 ≤ g_from[i], g_to[i] ≤ n

malware[i] = 0 or 1