Prerequisites: Graphs, DFS/BFS, Topological order.
Problem: You have to complete N courses. There are M requirements of the form “course a has to be completed before course b”. Find an order in which you can complete the courses. Output N space separated integers, describing the order of N courses which should be taken in order to complete all of them. If it’s not possible to complete all the courses, output -1.
Solution Approach: We need to take the courses in an ordering which satisfies the prerequisite constraints. This means that any course can only be taken when all its prerequisite courses are already completed. We can visualize this problem as a graph where courses are nodes and edge from one course to the next means that 1st node is a prerequisite of the 2nd. Then, we can visit a node only when all of its previous connected nodes leading to it are already visited. This is nothing but Topological ordering. We have used BFS for topological ordering. Refer previous problem where we’ve discussed in detail how to find topological ordering using BFS.
Time complexity: O(N + M) as we are using BFS.
Space complexity: O(N) as we need to use a queue in BFS.