Course Schedule

Problem

There are numCourses courses labelled 0 through numCourses - 1. You are given a list prerequisites of pairs [a, b] meaning "you must complete course b before you can take course a". Decide whether it is possible to finish every course, i.e. whether some ordering of all courses respects every prerequisite.

• There are at most 3,000 courses and at most 8,000 prerequisite pairs.
• Each pair contains two distinct course labels; pairs are not repeated.

Examples

• numCourses = 3, prerequisites = [[1, 0], [2, 1]] → true. A straight chain: take 0, then 1, then 2.
• numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2], [0, 3]] → false. The chain wraps back around into a 4-course cycle.
• numCourses = 5, prerequisites = [] → true. No constraints at all.

Hints

1. Draw each prerequisite as a directed edge. What property of the graph makes finishing impossible?
2. A course you can start right now is one with no unfinished prerequisites. After you finish it, which other courses become startable?
3. Detect a cycle in a directed graph: either Kahn's algorithm (repeatedly remove nodes with in-degree 0 and check whether all nodes were removed) or DFS with white/gray/black coloring.