Kill The Snipers

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Intuit

Problem statement

Ninja is playing a game in which he has to kill N number of snipers. The snipers are numbered from 0 to N-1. However, some snipers are being defended by other snipers which in turn may be defended by some other snipers, and they can not be killed directly. For example, if sniper A is being defended by sniper B, then 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 whether Ninja can win this game by killing all the snipers or not.

For Example : 
If N = 3 and defense = {{2,1}, {2,0}}.
There are a total of three snipers, and the sniper 1 and 0 both are defended by sniper 2. So, Ninja can kill sniper 2 first, and then he can kill the rest two snipers in any order. Hence, the answer is YES, as Ninja can kill all the snipers.
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 defending and the sniper defended
Output Format : 
For each test case, print “YES”, if Ninja can kill all the snipers. Print “NO” otherwise. 

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
2 0
Sample Output 1 :
YES
NO
Explanation For Sample Input 1 :
For the first test case, the defense diagram is shown in the below figure.

graph_input1_ex1

One possible way to win the fight is to kill the snipers in the order 0 → 1 → 2 → 3. So, the answer is YES, as Ninja can win the fight by killing all the snipers.

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

graph_input1_ex2

Ninja can not win the war as all the snipers are defended by other snipers.
Sample Input 2 :
2
3 3
0 1
1 2
0 2
3 3
0 1
1 0
1 2
Sample Output 2 :
YES
NO
Hint

Think of a DFS based approach.

Approaches (2)
DFS Approach

The idea here is to draw directed edges from each sniper who is defending to the sniper who is being defended. Then, we check whether there is a cycle present in the graph or not. If a cycle is present, that means the snipers can not be killed as they are being defended by each other. So, the answer is “NO” in that case. If there are no cycles present in the graph, then the answer is “YES”.

 

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.
  • Call a function isCyclePresent(N, graph), which returns true if there is a cycle present in the graph. Return true; if this function returns false, else return false.

 

bool isCyclePresent(N, graph[N][]):

 

  • Create two boolean arrays named as visited and stack and initialize them to false. The visited array is used to keep track of the visited nodes, and the stack array is used to keep track of the nodes that are already in the recursion stack.
  • Run a loop from i = 0 to N and do:
    • If visited[i] == false, i.e., if the current node is unvisited, we start the dfs function from this node. Let’s call this function as isCyclePresentUtil(graph, i, visited, stack). Note that the visited and the stack array should be passed by reference. If this function returns true, then simply return true.
  • Finally, return false.

 

bool isCyclePresentUtil(graph[N][], src, &visited[], &stack[]):

 

  • Make visited[src] and stack[src] = true.
  • Run a loop from i = 0 to graph[src].size and do:
    • If stack[graph[src][i]] == true, that means this node is already in the recursion stack. So, a cycle is present. Hence, we return true.
    • If visited[graph[src][i]] == false, then we call the function recursively by passing graph[src][i] as the src, i.e., isCyclePresentUtil(graph, graph[src][i], visited, stack). Return true, if this function returns true.
  • Finally, mark stack[src] as false as this node gets out of the recursive stack and return false.
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 dfs 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 contains a total of N nodes and M edge. So, the overall space complexity is O(N+M).

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