# Prerequisite Task

Posted: 21 Dec, 2020

Difficulty: Moderate

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

- So for detecting the cycle in the directed graph, we will perform the following steps:
- If we detect the cycle, then we return false else return true.

Approach 2

- The problem is also known as the
**topological sort**problem, which is to find a global order for all nodes in a**DAG**(Directed Acyclic Graph) with respect to their dependencies. - We can transform the given problem into a directed graph as described above. We will also create an INDEGREE[] array to store in-degree of each node, whenever we are adding a directed edge from U -> V, we will increase the value of INDEGREE[V]+=1.
- Now we perform the topological sorting on the graph using BFS. If we are successfully able to top sort our graph, that means there is no cycle in the graph, and we can finish each task.
- So for topological sorting in the directed graph, we will perform the following steps:
- We first start to take the independent tasks (no prerequisites or 0 INDEGREE).
- After taking the courses, we remove it and update the INDEGREE of its dependent tasks ( INDEGREE[V]-=1 ).
- Have a COUNT variable to keep track of taken independent tasks (0 INDEGREE ).
- Repeat the process until-
- If there is a cycle in the graph, which means there are still tasks left to be finished and no tasks have 0 INDEGREE remaining, i.e., COUNT != N.
- Else we finish all courses (COUNT == N), and we return true.

- Pictorial example of the approach

SIMILAR PROBLEMS

# Bellman Ford

Posted: 23 Jul, 2021

Difficulty: Moderate

# Floyd Warshall

Posted: 23 Jul, 2021

Difficulty: Moderate

# Root to Leaf Path

Posted: 23 Jul, 2021

Difficulty: Moderate

# Minimum Knight Moves

Posted: 20 Aug, 2021

Difficulty: Hard

# Collect Maximum Coins in Matrix

Posted: 29 Oct, 2021

Difficulty: Moderate