Course Schedule

Difficulty: Medium · Topic: Graphs

There are n courses 0…n-1. Each pair [a, b] in prerequisites means you must take b before a. Return True if you can finish every course — i.e. the dependency graph has no cycle (it's a DAG). Use a topological sort (Kahn's algorithm) and check that every node is processed.

Examples

course_schedule(2, [[1,0]])
→ true

Take 0, then 1.

course_schedule(2, [[1,0],[0,1]])
→ false

0 and 1 depend on each other.

Target complexity: time O(V + E), space O(V + E)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.