Prerequisite Task

Posted: 21 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1
  • 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.
Try Problem