Graphs

Question 1

210. Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]

Answer 1

Algorithm

1. Initialize a queue, Q to keep a track of all the nodes in the graph with 0 in-degree.
2. Iterate over all the edges in the input and create an adjacency list and also a map of node v/s in-degree.
3. Add all the nodes with 0 in-degree to Q.
4. The following steps are to be done until the Q
   becomes empty.
   4.1 Pop a node from the Q. Let’s call this node, N.
   4.2 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.
   4.3 Add the node N to the list maintaining
   topologically sorted order.
   Continue from step 4.1.

Takeaways:

1. Carefully define the parent child map.
2. Degree of child node should be increased while building the in-degree map
3. Initially add ALL nodes with degree 0
4. While processing the queue, add the child of current node to the queue only if its in-degree is zero.