Determine Whether All Courses Can Be Completed

Problem

There are numCourses courses numbered 0 through numCourses - 1. Each prerequisite pair [course, prerequisite] means the prerequisite must be completed first. Return whether it is possible to finish every course.

Function Contract

Implement canFinishCourses(numCourses, prerequisites).

Constraints & Assumptions

• 1 <= numCourses <= 200,000.
• 0 <= len(prerequisites) <= 500,000.
• Pairs are valid course IDs but may be duplicated.
• A self-dependency makes completion impossible.

Clarifying Questions to Ask

• Can duplicate prerequisite pairs appear? Yes; deduplicate edges or count and remove them consistently.
• Is an ordering required? No, return only a boolean.
• Are disconnected course groups allowed? Yes, all must be acyclic.
• What prevents completion? Any directed cycle.

Hint: Remove courses with no unmet prerequisites

Build outgoing edges and indegrees, enqueue every zero-indegree course, and count how many can be removed.

Example

numCourses = 2
prerequisites = [[1,0]]
output = true

numCourses = 2
prerequisites = [[1,0], [0,1]]
output = false

Evaluation Focus

• Builds edge direction and indegrees correctly.
• Handles duplicate edges without corrupting indegree counts.
• Processes disconnected nodes and isolated courses.
• Runs in O(v + e) time and space.

Extensions to Discuss

1. How would you return one valid course order?
2. How could DFS produce an explicit cycle?
3. How would you update the result after adding one prerequisite edge?