Course Schedule II

Posted: 4 Jan, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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:

 

  1. Firstly, initialize a queue, ‘Q’ to keep a track of all the nodes in the graph with 0 in-degree.
  2. 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’.
  3. Keep following the below steps until the ‘Q’ becomes empty.
  4. Pop a node from the ‘Q’. Let's call this node, ‘N’.
  5. 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’.
  6. Add the node 'N' to the list maintaining topologically sorted order.
  7. Continue from step 3.
Try Problem