Course Schedule II

Problem

There are numCourses courses numbered 0 to numCourses - 1, and a list of prerequisites where each pair [a, b] means course b must be completed before course a. Return any ordering of all the courses that satisfies every prerequisite. If no such ordering exists because the prerequisites are circular, return an empty list.

• There are at most 3,000 courses, and the prerequisite list can name every ordered pair of them at most once.
• Each pair has two distinct courses and no pair is repeated.

Examples

• numCourses = 3, prerequisites = [[1, 0], [2, 1]] → [0, 1, 2]. A straight chain has exactly one valid order.
• numCourses = 5, prerequisites = [[1, 0], [2, 0], [3, 1], [4, 1]] → [0, 1, 2, 3, 4] or any order with 0 before {1, 2} and 1 before {3, 4}; courses 2, 3, and 4 have no ordering constraint among themselves.
• numCourses = 2, prerequisites = [[0, 1], [1, 0]] → []. Circular.

Hints

1. Which course can always go first? What changes about the remaining courses once you have placed it?
2. Keep, for each course, a count of its unplaced prerequisites; courses whose count is zero are ready to be placed.
3. Topological sort. Kahn's algorithm produces the order directly; a DFS gives it as the reverse of the finishing order.