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.

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

Core idea (near-solution)

This is cycle detection in a directed graph. If there is a cycle, you cannot finish all courses. Use Kahn's algorithm (topological ordering) and check if you process all nodes.

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

• Invariant: nodes with indegree 0 are always safe to take next.
• Nodes with indegree 0 have no unmet prerequisites and can be taken safely.
• Removing them and updating indegrees preserves correctness of remaining prerequisites.
• If all nodes are removed, the order is valid; otherwise a cycle exists.

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.

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.