Skip to content

Course Schedule

Problem

There are numCourses courses labeled 0..numCourses-1. Given a list of prerequisite pairs [course, prereq], determine if it is possible to finish all courses (i.e., the prerequisite graph is a DAG).

Approach

BFS topological sort (Kahn's algorithm). If the resulting order contains fewer than numCourses nodes, a cycle exists.

When to Use

Cycle detection in a directed graph — "can all tasks be completed?", "is the dependency graph a DAG?". Topological sort that checks for leftover nodes. See also: topological_sort for the ordering itself.

Complexity
Time O(V + E)
Space O(V + E)

Implementation

course_schedule

Determine if all courses can be finished (cycle detection).

Problem

There are numCourses courses labeled 0..numCourses-1. Given a list of prerequisite pairs [course, prereq], determine if it is possible to finish all courses (i.e., the prerequisite graph is a DAG).

Approach

BFS topological sort (Kahn's algorithm). If the resulting order contains fewer than numCourses nodes, a cycle exists.

When to use

Cycle detection in a directed graph — "can all tasks be completed?", "is the dependency graph a DAG?". Topological sort that checks for leftover nodes. See also: topological_sort for the ordering itself.

Complexity

Time: O(V + E) Space: O(V + E)

can_finish 

can_finish(
    num_courses: int, prerequisites: list[list[int]]
) -> bool

Return True if all courses can be completed.

can_finish(2, [[1, 0]]) True can_finish(2, [[1, 0], [0, 1]]) False

Source code in src/algo/graphs/course_schedule.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """Return True if all courses can be completed.

    >>> can_finish(2, [[1, 0]])
    True
    >>> can_finish(2, [[1, 0], [0, 1]])
    False
    """
    adj: list[list[int]] = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue: deque[int] = deque(i for i in range(num_courses) if in_degree[i] == 0)
    visited = 0

    while queue:
        node = queue.popleft()
        visited += 1
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return visited == num_courses

find_order 

find_order(
    num_courses: int, prerequisites: list[list[int]]
) -> list[int]

Return a valid course order, or [] if impossible.

find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) [0, 1, 2, 3]

Source code in src/algo/graphs/course_schedule.py 
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """Return a valid course order, or [] if impossible.

    >>> find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
    [0, 1, 2, 3]
    """
    adj: list[list[int]] = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue: deque[int] = deque(i for i in range(num_courses) if in_degree[i] == 0)
    order: list[int] = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != num_courses:
        return []
    return order
tests/graphs/test_course_schedule.py
"""Tests for course schedule (cycle detection)."""

from algo.graphs.course_schedule import can_finish, find_order


class TestCanFinish:
    def test_no_prerequisites(self) -> None:
        assert can_finish(3, []) is True

    def test_simple_chain(self) -> None:
        assert can_finish(2, [[1, 0]]) is True

    def test_cycle(self) -> None:
        assert can_finish(2, [[1, 0], [0, 1]]) is False

    def test_larger_dag(self) -> None:
        assert can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) is True

    def test_larger_cycle(self) -> None:
        assert can_finish(3, [[0, 1], [1, 2], [2, 0]]) is False

    def test_single_course(self) -> None:
        assert can_finish(1, []) is True


class TestFindOrder:
    def test_valid_order(self) -> None:
        order = find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
        assert len(order) == 4
        assert order.index(0) < order.index(1)
        assert order.index(0) < order.index(2)
        assert order.index(1) < order.index(3)
        assert order.index(2) < order.index(3)

    def test_cycle_returns_empty(self) -> None:
        assert find_order(2, [[1, 0], [0, 1]]) == []

    def test_no_deps(self) -> None:
        order = find_order(3, [])
        assert sorted(order) == [0, 1, 2]

    def test_single_course(self) -> None:
        assert find_order(1, []) == [0]

Implement it yourself

Run: just challenge graphs course_schedule

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

course_schedule

Determine if all courses can be finished (cycle detection).

Problem

There are numCourses courses labeled 0..numCourses-1. Given a list of prerequisite pairs [course, prereq], determine if it is possible to finish all courses (i.e., the prerequisite graph is a DAG).

Approach

BFS topological sort (Kahn's algorithm). If the resulting order contains fewer than numCourses nodes, a cycle exists.

When to use

Cycle detection in a directed graph — "can all tasks be completed?", "is the dependency graph a DAG?". Topological sort that checks for leftover nodes. See also: topological_sort for the ordering itself.

Complexity

Time: O(V + E) Space: O(V + E)

can_finish 

can_finish(
    num_courses: int, prerequisites: list[list[int]]
) -> bool

Return True if all courses can be completed.

can_finish(2, [[1, 0]]) True can_finish(2, [[1, 0], [0, 1]]) False

Source code in src/algo/graphs/course_schedule.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """Return True if all courses can be completed.

    >>> can_finish(2, [[1, 0]])
    True
    >>> can_finish(2, [[1, 0], [0, 1]])
    False
    """
    adj: list[list[int]] = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue: deque[int] = deque(i for i in range(num_courses) if in_degree[i] == 0)
    visited = 0

    while queue:
        node = queue.popleft()
        visited += 1
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return visited == num_courses

find_order 

find_order(
    num_courses: int, prerequisites: list[list[int]]
) -> list[int]

Return a valid course order, or [] if impossible.

find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) [0, 1, 2, 3]

Source code in src/algo/graphs/course_schedule.py 
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """Return a valid course order, or [] if impossible.

    >>> find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
    [0, 1, 2, 3]
    """
    adj: list[list[int]] = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue: deque[int] = deque(i for i in range(num_courses) if in_degree[i] == 0)
    order: list[int] = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != num_courses:
        return []
    return order