Last Updated: 4 Jan, 2021
Course Schedule II
Hard
Asked in companies
You have been given ‘N’ courses and some courses may have prerequisites. Now consider a matrix ‘PREREQUISITES’ of size 'M' x 2 which represents that you must complete the course 'PREREQUISITES[i][1]' before the course 'PREREQUISITES[i][0]'.
Your task is to return the order of courses you should take to finish all courses.
Note:
If it is impossible to finish all courses, return an empty array. If there are multiple answers, return any one.
For example:
Input:
3 2
1 2
2 3
There are three courses to take. To start with, First course 3 is taken. Then course 2 is taken for which course 3 must be completed.
At last course 1 is taken for which course 2 must be completed. So the correct course order is [3,2,1].
Input Format:
The first line contains two integers 'N' and 'M' representing the number of courses and the number of prerequisite pairs.
The next ‘M’ lines in each test case contain a matrix ‘PREREQUISITES’ containing two integers denoting a prerequisite pair.
Output Format:
The only line contains a single integer 1 if the returned order of the courses is correct, otherwise 0.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Approaches
Our current algorithm is based on the idea of the BFS approach. We first process all the courses with 0 in-degree implying no prerequisite courses required. If we remove all these courses from the graph, along with their outgoing edges, we can find out the courses/nodes that should be processed next. These would again be the nodes with 0 in-degree. We can continuously do this until all the courses have been accounted for.
The steps are as follows:
- Firstly, initialize a queue, ‘Q’ to keep a track of all the nodes in the graph with 0 in-degree.
- Then Iterate over all the edges in the input and create an adjacency list and also a map of node v/s in-degree. Add all the nodes with 0 in-degree to ‘Q’.
- Keep following the below steps until the ‘Q’ becomes empty.
- Pop a node from the ‘Q’. Let's call this node, ‘N’.
- For all the neighbors of this node, ‘N’, reduce their in-degree by 1. If any of the nodes' in-degree reaches 0, add it to the ‘Q’.
- Add the node 'N' to the list maintaining topologically sorted order.
- Continue from step 3.
We need to get all the courses that have a particular course as a prerequisite. If a valid ordering of courses is possible, the course ‘A’ would come before all the other set of courses that have it as a prerequisite. This idea for solving the problem can be explored using a depth-first search.
The steps are as follows:
- Firstly, Initialize a stack that will contain the topologically sorted order of the courses.
- The construct the adjacency list using the edge pairs given in the input. An important thing to note about the input for the problem is that a pair such as [a, b] represents that the course b needs to be taken in order to do the course a. This implies an edge of the form b -> a. Please take note of this when implementing the algorithm.
- Now for each of the courses, we will run a depth-first search in case that node was not already visited in some other node's DFS traversal.
- Suppose we are executing the depth-first search for a node ‘N’. We will recursively traverse all of the neighbors of node ‘N’ which have not been processed before.
- Once the processing of all the neighbors is done, we will add the node ‘N’ to the stack. We are making use of a stack to simulate the ordering we need.
- When we add the node ‘N’ to the stack, all the nodes that require the node ‘N’ as a prerequisite (among others) will already be in the stack.
- Once all the nodes have been processed, we will simply return the nodes as they are present in the stack from top to bottom.