Course Schedule & Cycle Detection
There are numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before course a. Determine if you can finish all courses (i.e. check if the prerequisite graph is a Directed Acyclic Graph / DAG).
Requirements
- ✓Return true if all courses can be finished, false if there is a circular dependency.
- ✓Prerequisites graph can be disconnected (multiple components).
- ✓Graph can contain self-loops or duplicate edges.
- ✓Time complexity must be O(V + E) where V is numCourses and E is prerequisites.length.
Constraints & Scale
- —1 <= numCourses <= 2000
- —0 <= prerequisites.length <= 5000
- —prerequisites[i].length == 2
- —0 <= ai, bi < numCourses
Understand
Guided mode
Model the problem as a graph. What are vertices and edges? What condition makes it impossible to complete all courses?
Context & Constraints — Human Reviewed
Directed graph where vertices are courses and directed edge (b -> a) represents dependency. If the graph contains a directed cycle (e.g. A -> B -> C -> A), no course in the cycle can ever be taken first, making completion impossible.
Trade-offs
- ⚖Kahn's Algorithm (BFS with In-degrees): Natural and iterative; directly produces topological order.
- ⚖DFS with 3-state coloring: Recursion-based; detects cycles efficiently in memory.
Concepts used in this stage