Course Schedule

Given numCourses and a list of prerequisite pairs, determine if you can finish all courses.

Each pair [a, b] means you must take course b before course a.

Why this is worth learning

A prerequisite pair [a,b] is a directed edge b->a. A course becomes available when all incoming requirements have been removed, not merely when one predecessor has finished.

Before coding: one-minute experiment

For prerequisites [1,0], [2,0], [3,1], [3,2], when does course 3 become available?

Function signature

func CanFinish(numCourses int, prerequisites [][]int) bool

Inputs / outputs

• numCourses: total number of courses labeled 0..numCourses-1.
• prerequisites: list of edges b -> a.
• Return: true if all courses can be completed.

Example

numCourses = 2
prerequisites = [[1,0]]
Output: true

numCourses = 2
prerequisites = [[1,0],[0,1]]
Output: false

Constraints

• 1 <= numCourses <= 200_000
• Every prerequisite has exactly two labels in 0..numCourses-1. Duplicate pairs, if supplied, must be counted consistently in adjacency and indegree.

Core idea (near-solution)

A brute scheduling model repeatedly scans unfinished courses and takes one whose prerequisites are all finished. Avoid rechecking every prerequisite after every choice by storing each course's count of unfinished incoming obligations. Processing a course decrements exactly the counts for courses that depend on it; zero means ready. This is Kahn's topological process. It must include isolated courses and finish all vertices. If the ready set empties early, every remaining vertex has a predecessor in the remainder; following those predecessors in a finite graph proves a cycle.

Invariant: nodes with indegree 0 are always safe to take next.

Algorithm (step-by-step)

1. Build adjacency list and indegree counts.
2. Push all nodes with indegree 0 into a queue.
3. Pop nodes, decrement indegree of neighbors, enqueue any that reach 0.
4. If you processed numCourses nodes, return true; otherwise false.

Correctness sketch

Maintain indegree as the number of incoming edges from unprocessed vertices. It is correct initially by construction. Removing a queued zero-indegree vertex satisfies exactly its outgoing dependencies, so decrementing each corresponding target preserves the invariant. Every emitted vertex is therefore schedulable after the emitted prefix. If vertices remain and none has zero indegree, repeatedly following a remaining incoming edge in the finite residual graph eventually repeats a vertex, proving a directed cycle. Conversely, a cycle can never lose all its internal incoming dependencies. Hence processing all vertices is equivalent to feasibility.

Trace (hand walkthrough)

Example input:
numCourses = 2
prerequisites = [[1,0]]
Output: true

numCourses = 2
prerequisites = [[1,0],[0,1]]
Output: false

Walk:
- case1 indegree: [0,1], queue [0] -> take 0 then 1 -> true
- case2 indegree: [1,1], queue empty -> cycle -> false

Pitfalls to avoid

• Reversing edge direction for prerequisites (b -> a).
• Forgetting to include courses with no edges in the initial queue.

Debugging lens

Draw arrows before building arrays. Count every edge consistently in both indegree and adjacency. Include isolated vertices and a disconnected cyclic component in tests.

Complexity

• Time: O(V + E)
• Extra space: O(V + E).

Implementation notes (Go)

• Build adjacency lists and indegree counts.
• Use a queue of 0-indegree nodes; process all nodes including isolated ones.

Reconstruction checkpoint

Courses 0 through 4 have prerequisite edges 0→1, 1→0, and 2→3; course 4 is isolated. What can Kahn’s algorithm process, and why is that insufficient to return true?

Return to Graph General · Module quiz