Neural Mastery
← Practice
Course Schedule: Cycle Detection in Directed Graphmedium

Course Schedule: Cycle Detection in Directed Graph

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Determine whether a course dependency graph contains cycles using Kahn's BFS topological sort.

Related Skills

Task

Implement can_finish_courses(numCourses, prerequisites): track in-degrees. Enqueue all courses with in-degree 0. As each course is processed, decrement neighbors' in-degrees. Return True if all courses are visited.

Function Signature

can_finish_courses(numCourses: int, prerequisites: list[list[int]]) -> bool

Examples

Example 1: Linear Prerequisite Chain
Input: numCourses = 2 prerequisites = [[1, 0]]
Output: True
Example 2: Mutual Prerequisite Deadlock
Input: numCourses = 2 prerequisites = [[1, 0], [0, 1]]
Output: False

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= len(prerequisites) <= 5000
Python3Saved ✓
def can_finish_courses(numCourses: int, prerequisites: list[list[int]]) -> bool:
"""numCourses: total courses labeled 0 to numCourses - 1.
prerequisites: list of [dest, src] meaning you must take course src before course dest.
Return True if it is possible to finish all courses (graph is acyclic), False otherwise."""
# Your implementation here
pass

Case 1: Linear Prerequisite Chain
Input: numCourses = 2 prerequisites = [[1, 0]]
Expected: True
Case 2: Mutual Prerequisite Deadlock
Input: numCourses = 2 prerequisites = [[1, 0], [0, 1]]
Expected: False