Problem of the day
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.
If it is impossible to finish all courses, return an empty array. If there are multiple answers, return any one.
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].
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.
4 4
2 1
3 1
4 2
4 3
1
There are a total of 4 courses to take. To take course 4 you should have finished both courses 2 and 3.
Both courses 2 and 3 should be taken after you finish course 1. So one correct course order is [1,2,3,4]. Another correct ordering is [1,3,2,4].
When the ordering is one of the above two sets then output is 1.
2 1
2 1
1
2 <= 'N' <= 10^5
0 <= 'M' <= 10^5
Where ‘PREREQUISITES’ denotes the prerequisites matrix.
Time limit: 1 sec
Can you think of using the BFS approach?
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:
O(N + M), where ‘N’ is the number of courses and ‘M’ is the number of prerequisites pairs.
Since the time complexity of this method is the same as the time complexity of the Breadth-First Search traversal i.e O(N + M) time, Thus the overall time complexity will be O(N + M).
O(N), where ‘N’ is the number of courses.
Since we are storing the nodes with in-degree as 0 in a queue and the queue will be of size N, Thus the overall space complexity will be O(N).