Last Updated: 25 Dec, 2020
Course Schedule
Easy
Asked in companies
You are a student of Netaji Subhas Institute of Technology. You have to take ‘N’ number of courses labelled from 1 to N to complete your B.Tech Degree.
Some courses may have prerequisites, for example, to take course 1 you have to first take course 2, which is expressed as a pair: [1, 2]. Now, your task is to find is it possible for you to finish all courses.
Note: There are no duplicate pairs in the prerequisites array.
For example-
If N = 2 and prerequisite = [[1, 2]]. Then, there are a total of 2 courses you need to take. To take course 1 you need to finish course 2. So, it is possible to complete all courses.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the total number of courses and the total number of prerequisites, respectively.
From the second line of each test case, the next M lines represent the prerequisites for courses. Every line contains two single space-separated integers representing a prerequisite pair.
Output Format:
For each test case, the only line of output will print “Yes” if you can complete the courses. Else print “No”.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 5000
0 <= M <= min(5000, (N * (N - 1)) / 2)
1 <= prerequisites[i][0] <= N
1 <= prerequisites[i][1] <= N
Time Limit: 1 sec
Approaches
The key observation here is that we need to consider the number of courses as vertices of a graph and prerequisites as directed edges of a graph.
Now the problem boils down to find if a cycle exists in the directed graph or not. If a cycle exists, no topological ordering exists and therefore it is impossible to take all courses.
Now, there is a cycle in the graph only if there is a back edge present in the graph. To detect a back edge, we will keep track of vertices currently in the recursion stack of function for DFS traversal. If a vertex is reached that is already in the recursion stack, then there is a cycle in the graph.
Here is the complete algorithm:
- Create a graph using the ‘prerequisites’ array.
- We initialise two arrays of ‘visited’ and ‘recursionStack’ to keep track of the visited vertices and vertices that are currently in the recursion stack, respectively.
- We iterate over all vertices of the graph and if the vertex is unvisited, we call the ‘isCycle’ function from that vertex. The ‘isCycle’ function works as follows:
- Mark the current vertex true in the ‘visited’ and ‘recursionStack’ array.
- Find all the adjacent vertices of the current vertex
- If an adjacent vertex is not visited
- Recursively call the ‘isCycle’ function for the adjacent vertex.
- If the recursive function returns true, then return true.
- Else if adjacent vertex is already visited and already marked in the ‘recursionStack’ array.
- Return true.
- If an adjacent vertex is not visited
- Finally, unmark the vertex from the ‘recursionStack’ array and return false.
- If the ‘isCycle’ function returns true, then return “No”.
- Finally, return “Yes”.
In this approach, we will use Kahn’s algorithm to detect cycle in a directed graph.
Here is the algorithm:
- Create a graph using the ‘prerequisites’ array.
- We compute indegree(number of incoming edges) for each vertex present in the graph.
- We initialise an integer variable ‘visited’ to 0, representing the count of visited nodes.
- Pick all vertices with indegree 0 and add them in a queue.
- We do the following operations until the queue becomes empty.
- Remove a vertex from the queue.
- Increment ‘visited’ by 1.
- Decrement the indegree of all its adjacent vertices by 1.
- If indegree of adjacent vertices is reduced to 0, then add them to the queue.
- If ‘visited’ is equal to ‘N’, then return “Yes” else return “No”.