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 ith bidirectional connection connects g_from[i] and g_to[i]. Some of the nodes are infected with malware. They are listed in the array malware, where if malware[i] = 1 node is infected, and if malware[i] = 0, node is not infected.
Any infected node infects other non-infected nodes, which are directly connected. This process goes on until no new infected nodes 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):
- 1.
int g_nodes: the number of nodes - 2.
int g_from[]: one end of the connections - 3.
int g_to[]: another end of the connections - 4.
int malware[]: 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 [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:
1 ≤ g_nodes ≤ 10^30 ≤ g_edges ≤ min(g_nodes*(g_nodes-1)/2, 10^3)1 ≤ g_from[i], g_to[i] ≤ nmalware[i] = 0 or 1.
input:
output: