# Minimize Malware Spread II

Posted: 31 Mar, 2021

Difficulty: Hard

#### You are given a network of ‘N’ nodes numbered from 0 to ‘N-1’. This network is represented using an adjacency matrix ‘GRAPH’ of size ‘N’ x ‘N’. You are also given an array ‘INITIAL’ of size ‘M’, which contains the nodes that are initially infected by malware. If there is a direct connection between two nodes and at least one of them is infected by malware, both nodes will be infected by the malware. This malware spread will continue until no more nodes are left, or no more nodes can be infected by this manner.

#### Let us define a variable ‘INFECTED’ to the total number of infected nodes by the malware spread. Your task is to remove exactly one node from the array ‘INITIAL’ such that it results in the ‘minimum’ value of ‘INFECTED’.

#### Note :

```
1. If GRAPH[X][Y] = 1, then the node ‘X’ is directly connected to a node ‘Y’. Otherwise, there is not a direct connection between ‘X’ and ‘Y’.
2. If we remove a node, we must also remove its connections to any other node.
3. If multiple such nodes exist that can minimize the value of ‘INFECTED’, you have to find the node with the smallest index.
4. All nodes in the array ‘INITIAL’ are unique.
5. You have to return the ‘index’ of the node, not the minimum value of the ‘INFECTED’.
```

##### Input Format :

```
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains two positive integers, ‘N’ and ‘M’, denoting the number of nodes in the network and the number of initially infected nodes respectively.
The following ‘N’ lines of each test case contain ‘N’ integers each, representing the adjacency matrix ‘GRAPH’.
The last line of input contains ‘M’ space-separated non-negative integers, denoting the elements of the array ‘INITIAL’.
```

##### Output Format :

```
For each test case, print the ‘index’ of the node that, after removing, would minimize the value of ‘INFECTED’, as described in the problem statement.
Output for each test case will be printed in a separate line.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 5
2 <= N <= 100
0 <= GRAPH[i][j] <= 1, GRAPH[i][j] == GRAPH[j][i]
GRAPH[i][i] == 1
1 <= M <= N
0 <= INITIAL[i] < N
Time Limit: 1sec
```

Approach 1

- The idea here is to use the BFS to calculate how many nodes will be infected after removing the
**i**th node from the array**INITIAL**. - So, we have to run the
**BFS**for each node in the initial array. - First, create a HashSet named
**infectedNodes**that contains all initially infected nodes. - Declare a variable
**ans**to store the final answer, initialize it with 0. - Also, declare a variable
**minCount**to store the minimum value of**INFECTED**, initialize it with INT_MAX. - Now, we have to traverse through the array
**initial**, let it be**cur**, in each iteration do:- Remove the node
**cur**from the array initial, and from the graph itself,**infectedNodes.remove(cur)**. - Call the function
**bfs**and pass**graph**,**infectedNodes**, and**cur**. It returns the number of nodes that are infected after the malware spread. Let the return value of this function is store in the variable**cnt**. - We have to update our
**ans**if the return value of**bfs**is smaller than**minCount**,**or**if equal**and**index that is**cur**is smaller than**ans**. - So, if (
**cnt**<**minCount**or (**cnt**==**minCount**and**cur**<**ans**), then- minCount = cnt.
- ans = cur.

- Before completing the current iteration, we must again
**insert**the removed node, i.e.,**cur,**into the HashSet**infectedNodes**,**infectedNodes.insert(cur)**.

- Remove the node
- Finally, return the
**ans**.

**int bfs(int[][] graph, HashSet infectedNodes, int cur):**

- Create a queue named
**q**that will contain all the nodes which are going to be explored. - Now,
**push**all the nodes of the HashSet**infectedNodes**into queue**q**. - Run a
**while**loop until the queue become**empty**:- Store the
**front**element of the queue in the variable**v**, and also remove it. - Run a for loop from
**i**= 0 to**i**<**graph[v].size()**to traverse through all the direct connections of node**v**, in each iteration do:- If
**i != cur**and**graph[v][i] == 1**and**!infectedCount(i)**, then push i into the queue, and insert the same into the HashSet.

- If

- Store the
- Finally,
**infectedNodes**will contain all the infected nodes after the malware spread and after the removal of**cur**. - Return the
**size**of**infectedNodes**.

Approach 2

- The idea is very similar to approach 1. The only difference is that we are using DFS here.
- So, we have to run the
**DFS**for each node in the initial array. - First, create a HashSet named
**infectedNodes**that contains all initially infected nodes. - Declare a variable
**ans**to store the final answer, initialize it with 0. - Also, declare a variable
**minCount**to store the minimum value of**INFECTED**, initialize it with INT_MAX. - Now, we have to traverse through the array
**initial**, let it be**cur**, in each iteration do:- Remove the node
**cur**from the array initial, and from the graph itself,**infectedNodes.remove(cur)**. - Create a variable
**cnt**to store the final number of infected nodes after the malware spread, after removing**cur**. - Create a HashSet named
**vis**, which is used to keep track of all**visited**nodes and insert**cur**into the vis. - For
**each node**in HashSet**infectedNodes**, let it be**v**, and which is not equal to the**cur**call the function**dfs**and pass**graph**,**vis**,**v**,**cnt**. It will increment the value of**cnt**if any other nodes will be infected and**insert**that node into the HashSet**vis**. - We have to update our
**ans**if**cnt**is smaller than**minCount**,**or**if equal**and**index that is**cur**is smaller than**ans**. - So, if (
**cnt**<**minCount**or (**cnt**==**minCount**and**cur**<**ans**), then- minCount = cnt.
- ans = cur.

- Before completing the current iteration, we must again
**insert**the removed node, i.e.,**cur,**into the HashSet**infectedNodes**,**infectedNodes.insert(cur)**.

- Remove the node
- Finally, return the
**ans**.

**void dfs(int[][] graph, HashSet vis, int v, int cnt):**

- If
**v**is already present in the**vis**, then simply**return**. - Insert
**v**into the**vis.** - Increment
**cnt**by 1. - Run a for loop from
**i**= 0 to**i**<**graph[v].size()**to traverse through all the direct connections of node**v**, in each iteration do:- If
**graph[v][i] == 1**and**i != v**, then again call the function**dfs**(graph, vis, i, cnt).

- If

SIMILAR PROBLEMS

# Get DFS Path

Posted: 22 Jul, 2021

Difficulty: Easy

# Get Path using BFS

Posted: 22 Jul, 2021

Difficulty: Easy

# Bellman Ford

Posted: 23 Jul, 2021

Difficulty: Moderate

# Floyd Warshall

Posted: 23 Jul, 2021

Difficulty: Moderate

# Collect Maximum Coins in Matrix

Posted: 29 Oct, 2021

Difficulty: Moderate