Course Schedule

Problem

There are numCourses courses, labeled 0 to numCourses - 1. Some courses have prerequisites, given as pairs [a, b] meaning "to take course a, you must first take course b." Return true if it's possible to finish all courses (i.e. the prerequisite requirements can all be satisfied), or false otherwise. (LeetCode 207.)

Examples

Constraints

up to 2000 courses, up to 5000 prerequisite pairs.

Attempt it first

Model each prerequisite pair [a, b] as a directed edge b → a ("b must come before a"). The question "can all courses be finished" is then exactly this module's Topological Sort concept lesson's central question: does a valid ordering of this directed graph exist at all? Before opening anything, recall precisely what property of a directed graph determines whether it does.