Kill The Snipers II

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
9 upvotes
Asked in company
Adobe

Problem statement

Ninja is playing a game in which he has to kill N number of snipers, and killing each sniper takes one unit of time. The snipers are numbered from 0 to N-1. However, some snipers are being defended by other snipers, and they can not be killed directly. For example, if sniper A is being defended by sniper B, Ninja has to kill sniper B first, and then only he can kill sniper A.

So, you are given a “defense” array, where each element contains two integers, say A, B, which means sniper B is defended by sniper A. Your task is to find out the minimum time needed to kill each sniper.

Note : 
If multiple snipers are defending a single sniper, then to kill this sniper, Ninja has to kill all its defenders first.

It is guaranteed that it is possible to kill all the snipers.
For Example : 
If N = 3 and defense = {{2,1}, {2,0}}.

There are three snipers, and the sniper 1 and 0 both are defended by sniper 2. So, Ninja can kill sniper two first, which takes 1 unit of time. Then he can kill the rest two snipers in any order. 

If he kills the 1st sniper first and then the 0th sniper, then the time needed to kill each sniper will be {3, 2, 1}. If he kills the 0th sniper first and then the 1st sniper, then the time will be {2, 3, 1}. So, considering both the cases, the minimum time needed to kill the 0th sniper is 2. The minimum time needed to kill the 1st sniper is also 2, and the minimum time needed to kill the 2nd sniper is 1. So, the final answer is {2, 2, 1}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains two space-separated integers N and M, denoting the total number of snipers and the number of elements in the array “defense”.

Then M lines follow. Each line contains two space-separated integers denoting the sniper who is being defended and the sniper who is defending.
Output Format : 
For each test case, print N space-separated integers. Each integer denotes the minimum time needed to kill i-th sniper.  

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 <= 100
2 <= N <= 5000
1 <= M <= 5000
0 <= defense[i][0], defense[i][1] <= N-1

Time limit: 1 sec
Sample Input 1 :
2
4 3
1 2
0 3
2 3
3 3
0 1
1 2
0 2
Sample Output 1 :
1 1 2 3
1 2 3
Explanation For Sample Input 1 :
For the first test case, the defense diagram is shown in the below figure.

graph_input1_ex1

For the second test case, the defense diagram is shown in the below figure.

graph_input1_ex2

Sample Input 2 :
2
4 3
0 1
1 2
2 3
4 3
2 1
2 0
0 3
Sample Output 2 :
1 2 3 4
2 2 1 3
Hint

Think of a BFS based approach using Topological sorting.

Approaches (1)
Topological Sorting

The idea here is to draw directed edges from each sniper who is defending to the sniper who is being defended. We are using a BFS based approach and trying to find a topological order of the graph. So, each child node takes one more unit of time than the parent node.

So, we first find the in-degree of each node. Push all the nodes that have a 0 in-degree to the queue. Initialize the answer for each node to 0. We do a BFS, and for each current node, we decrease the in-degree of its neighbours by 1. Now, if the in-degree of any node becomes 0 in the process, then make ans[neighbour] = ans[current] + 1 and push that node to the queue as well.

 

Algorithm

 

  • Create the graph by making N nodes, where each node denotes a sniper. Draw directed edges from each sniper who is defending to the sniper who is being defended.
  • Create an in-degree array of size N to store each node’s in-degree, i.e., the number of incoming edges to each node, and initialise all the elements of this array to 0 initially.
  • Run a loop from i = 0 to N and do:
    • Run a loop from j = 0 to graph[i].size and do:
      • Increment indegree[graph[i][j]].
  • Create an answer array of size N to store the minimum time needed to kill each sniper. Let’s name it ans. Create an empty queue q.
  • Run a loop from i = 0 to N and do:
    • If indegree[i] == 0, then make ans[i] = 1 and push i to the queue as well.
  • While q is not empty, do:
    • Keep the first element of the queue in a curr variable and pop the queue’s first element.
    • Run a loop from i = 0 to graph[curr].size and do:
      • Decrement indegree[graph[curr][i]].
      • If indegree[graph[curr][i]] == 0, then make ans[graph[curr][i]] = ans[curr] + 1 and push graph[curr][i] to the queue as well.
  • Finally, return the ans array.
Time Complexity

O(N+M), where ‘N’ and ‘M’ denote the number of snipers and the “defense” array size, respectively.

 

We are traversing each node of the graph, and the BFS function runs for each edge of the graph, so the overall time complexity is O(N + M).

Space Complexity

O(N+M), where ‘N' and ‘M’ denote the number of snipers and the “defense” array size, respectively.

 

The graph array contains a total of N nodes and M edges. So, the overall space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Kill The Snipers II
Full screen
Console