Prerequisite Task

Moderate
0/80
Average time to solve is 35m
13 upvotes
Asked in companies
AdobeFacebookIntuit

Problem statement

You are given a positive integer ‘N’ denoting the number of tasks you need to finish. You can directly start performing any task, but some tasks have some prerequisites, i.e. to perform some task you may first need to complete some other tasks.

You are given a list of pairs of dependencies in the form of ( U, V ) which means to perform task ‘U’ you first need to finish the task ‘V’. You need to report whether it is possible to complete all the tasks or not. Return true if it is possible to finish all the tasks else return false.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the number of the tasks and dependencies respectively.

The next ‘M’ lines of each test case contain two space-separated positive integers in the form of ( U, V ) denoting that to perform a task ‘U’ you first need to finish the task ‘V’.
Output Format: 
The only line of output of each test case should contain  “Yes” (without quotes) if it is possible to finish all the tasks else “No” (without quotes).
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N, M <= 10^4
1 <= U, V <= N 

Time Limit: 1 sec
Sample Input 1:
2
3 3
1 2
3 2
1 3
2 2
1 2
2 1
Sample Output 1:
Yes
No
Explanation for sample input 1:
Test case 1:
In the first case to perform task 1, we need to do task 2 and 3. And to finish task 3 we need to complete task 2 as well, so we order should be  2->3->1 which is possible   

Test case 2:
In the second test, case task 1 is depending upon task 2, and task 2 is also depending upon task 1 so we there is a cyclic dependency, and we can’t finish the task in this case.
Sample Input 2:
2
3 2
1 2
2 3
4 3
1 4
2 3
3 2
Sample Output 2:
 Yes
 No
Hint

Detect the cycle in the directed graph

Approaches (2)
DFS
  • We can transform the given problem into a directed graph. We will consider tasks as nodes and dependency as edges so for building the graph we add a directed edge from U  -> V, for every pair of vertices given in the dependency list.
  • Now if we carefully observe, then we can notice that all the tasks can only be finished only when there is no directed cycle in the graph. Why? Because if there is a cycle present in the graph that means we have tasks waiting to be performed circularly and we can not perform any of these tasks due to their dependencies on the next task present in the cycle.
    • So for detecting the cycle in the directed graph, we will perform the following steps:
      We will use two boolean arrays named as VISITED[] and IN_STACK[]. The VISITED[i] will be true if the ith node is visited and IN_STACK[i] will be true when the ith node is visited but not yet explored and present in our calling stack.
    • We will perform the DFS and mark the node visited as soon as we reach it.
    • Now we will traverse on its adjacent node if any node has IN_STACK[NODE] = true that means this node is currently not explored whole and is present in our stack, this is the case when we can say that there is a cycle present in our graph.
  • If we detect the cycle, then we return false else return true.
Time Complexity

O(N + M), where ‘N’ is the number of tasks and ‘M’ is the number of dependencies.

As we are traversing each vertex and edge in the graph once.

Space Complexity

O(N), where ‘N’ is the number of tasks.

In the worst case, recursion can have ‘N’ call in the function stack.
 

Code Solution
(100% EXP penalty)
Prerequisite Task
Full screen
Console