Last Updated: 19 Feb, 2021

Kill The Snipers

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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.

Solve now

02 Approach

The idea is the same as the previous approach, i.e., our major focus is to detect a cycle in the directed graph. But here we are using a BFS based approach, and we are trying to find a topological order of the graph. If topological sorting is possible, then the graph doesn’t contain any cycle; otherwise, a cycle is present.

So, we first find the in-degree of each node. Push all the nodes that have a 0 indegree to the queue. Then we do a BFS, and for each current node, we decrease the in-degree of its neighbors by 1. Now, if the in-degree of any node becomes 0 in the process, push that node to the queue as well. Keep a count variable to keep track of the number of nodes that have entered the queue. After the BFS is over, if the value of the count is equal to N, then there is no cycle; otherwise, a cycle is present.

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 an indegree array of size N to store each node’s in-degree, i.e., the number of incoming edges to each node, and initialize 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 a queue q. Push all the nodes to the queue that have a 0 indegree.
Create a count variable and initialize it to 0.
While q is not empty, do:
- Keep the first element of the queue in a curr variable and pop the queue’s first element.
- Increment the count variable.
- Run a loop from i = 0 to graph[curr].size and do:
  - Decrement indegree[graph[curr][i]].
  - If indegree[graph[curr][i]] == 0, then push graph[curr][i] to the queue.
If count == N, then we return false as there is no cycle present in the graph. Return true otherwise.

Solve now