Course Schedule II
Last Updated: 4 Jan, 2021
Difficulty: Hard
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 course 'PREREQUISITES[i][1]' before the course 'PREREQUISITES[i][0]'.
Your task is to return the ordering 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.
Input Format:
The first line of input contains an integer 'T' representing the number of the test case.
The first line of each test case contains an integer ‘N’ representing the number of courses.
The second line of each test case contains a given integer ‘M’ representing 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:
For each test case, print a single integer 1 if the returned order of the courses is correct otherwise we return 0.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
2 <= N <= 100
1 <= M <= min(100,N(N-1)/2)
1 <= PREREQUISITES[i][0], PREREQUISITES[i][1] <= N
Where ‘PREREQUISITES’ denotes the prerequisites matrix.
Time limit: 1 sec
Approach 1
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.
Approach 2
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.
SIMILAR PROBLEMS
COUNT ISLANDS
Posted: 14 Sep, 2022
Difficulty: Moderate
Capturing Grid
Posted: 14 Sep, 2022
Difficulty: Moderate
The Summit
Posted: 15 Sep, 2022
Difficulty: Easy
Rotting Oranges
Posted: 15 Sep, 2022
Difficulty: Moderate
Distance to a Cycle in Undirected Graph
Posted: 7 Nov, 2022
Difficulty: Moderate
