DSA Course Schedule

The problem

Course Schedule asks whether a set of courses can all be finished. Each pair names a course and one prerequisite, a course that must be finished before it.

The answer is True when some order finishes every course. The answer is False when no order works. A cycle in the prerequisites is exactly what makes an order impossible, because each course on the cycle waits on another course on the cycle.

cases = [
    (4, [(1, 0), (2, 0), (3, 1), (3, 2)], True),
    (3, [(1, 0), (2, 1), (0, 2)], False),
    (2, [(1, 0), (0, 1)], False),
    (1, [], True),
]
for num, pairs, expected in cases:
    print("courses", num, "pairs", pairs, "->", expected)

The first plan branches and rejoins, since course 3 needs both course 1 and course 2. The middle plans loop back on themselves. The last plan is a single course with nothing before it.

Intuition: one visited set is enough, until it is not

The first idea searches the graph from each course and keeps a set of visited courses. Meeting a visited course feels like finding a loop. That feeling is wrong on any plan where two paths rejoin.

The first plan rejoins at course 3. A search reaches course 3 down one path, finishes it, and later arrives down the other path. The second arrival is harmless, but a single set cannot tell it apart from a loop.

def naive(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
    for v in graph:
        graph[v] = sorted(graph[v])
    visited = set()

    def dfs(node):
        if node in visited:
            return False
        visited.add(node)
        for nb in graph[node]:
            if not dfs(nb):
                return False
        return True

    for v in range(num_courses):
        if not dfs(v):
            return False
    return True

print("plan one, naive answer:", naive(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
print("plan one, correct answer: True")

The naive search answers False for a plan that a student could finish in the order 0, 1, 2, 3. The missing piece is a distinction between a course on the current path and a course finished earlier. Three colours supply that distinction.

Brute force: take any ready course, sweep by sweep

The brute force builds an order directly. A course is ready when every prerequisite is already taken. Each sweep scans the remaining courses, collects the ready ones, and takes them all at the end of the sweep.

A sweep that finds no ready course while courses remain proves a cycle. Every remaining course is waiting on another remaining course, and that waiting must loop. A counter records the prerequisite checks each sweep spends.

def can_finish_brute(num_courses, pairs):
    prereqs = {i: set() for i in range(num_courses)}
    for course, prereq in pairs:
        prereqs[course].add(prereq)
    taken = set()
    remaining = set(range(num_courses))
    checks = 0
    while remaining:
        ready = []
        for course in sorted(remaining):
            ok = True
            for p in sorted(prereqs[course]):
                checks += 1
                if p not in taken:
                    ok = False
                    break
            if ok:
                ready.append(course)
        if not ready:
            return False, checks
        taken.update(ready)
        remaining -= set(ready)
    return True, checks

for num, pairs in [(4, [(1, 0), (2, 0), (3, 1), (3, 2)]), (3, [(1, 0), (2, 1), (0, 2)]), (2, [(1, 0), (0, 1)])]:
    result, checks = can_finish_brute(num, pairs)
    print("courses", num, "->", result, "- prerequisite checks:", checks)

The valid plan costs repeated sweeps, and each sweep retests prerequisites that were already tested. The retesting is the waste. A search that remembers finished courses never pays it.

The optimal solution: three colours separate a cycle from a rejoin

The state is a colour per course. White means untouched, grey means on the path the search is walking now, and black means fully finished. An edge to a grey course closes a cycle, and an edge to a black course is always safe.

The search is depth-first, following edges from a prerequisite to the courses that need it. A course turns grey on entry and black when every course beyond it checks out. One grey hit anywhere fails the whole plan.

def can_finish(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
    for v in graph:
        graph[v] = sorted(graph[v])
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {i: WHITE for i in range(num_courses)}

    def dfs(node):
        colour[node] = GREY
        for nb in graph[node]:
            if colour[nb] == GREY:
                return False
            if colour[nb] == WHITE:
                if not dfs(nb):
                    return False
        colour[node] = BLACK
        return True

    for v in range(num_courses):
        if colour[v] == WHITE:
            if not dfs(v):
                return False
    return True

cases = [
    (4, [(1, 0), (2, 0), (3, 1), (3, 2)], True),
    (3, [(1, 0), (2, 1), (0, 2)], False),
    (2, [(1, 0), (0, 1)], False),
    (1, [], True),
]
for num, pairs, expected in cases:
    result = can_finish(num, pairs)
    print("courses", num, "->", result, "| expected:", expected, "| match:", result == expected)

All four cases from the start of the article pass. The rejoining plan now answers True, because course 3 is black, not grey, when the second path reaches it. The two looping plans still fail, and they fail on grey edges.

Walkthrough: colouring the first plan

The walk runs the search on the four-course plan. The outer loop starts at course 0, the smallest untouched course. Each line prints one colour change in the order it happens.

pairs = [(1, 0), (2, 0), (3, 1), (3, 2)]
graph = {i: [] for i in range(4)}
for course, prereq in pairs:
    graph[prereq].append(course)
for v in graph:
    graph[v] = sorted(graph[v])
WHITE, GREY, BLACK = 0, 1, 2
colour = {i: WHITE for i in range(4)}
names = {0: "white", 1: "grey", 2: "black"}

def dfs(node):
    colour[node] = GREY
    print("enter", node, "- now grey")
    for nb in graph[node]:
        if colour[nb] == BLACK:
            print("neighbour", nb, "is black - safe, skip")
        elif colour[nb] == WHITE:
            dfs(nb)
    colour[node] = BLACK
    print("finish", node, "- now black")

for v in range(4):
    if colour[v] == WHITE:
        dfs(v)
print("final colours:", [names[colour[i]] for i in range(4)])

Course 3 turns black deep inside the walk, under course 1. When course 2 is entered later, its edge to course 3 reads black and is skipped. No edge ever reads grey, so the plan is possible.

Complexity

The colour search enters each course once and reads each edge once, so its time is proportional to the courses plus the pairs, written O(V + E). The colour map holds one entry per course, so its space is O(V).

def counted(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
    for v in graph:
        graph[v] = sorted(graph[v])
    colour = {i: 0 for i in range(num_courses)}
    visits = [0]
    edges = [0]

    def dfs(node):
        colour[node] = 1
        visits[0] += 1
        for nb in graph[node]:
            edges[0] += 1
            if colour[nb] == 1:
                return False
            if colour[nb] == 0:
                if not dfs(nb):
                    return False
        colour[node] = 2
        return True

    for v in range(num_courses):
        if colour[v] == 0:
            if not dfs(v):
                break
    return visits[0], edges[0]

def brute_checks(num_courses, pairs):
    prereqs = {i: set() for i in range(num_courses)}
    for course, prereq in pairs:
        prereqs[course].add(prereq)
    taken = set()
    remaining = set(range(num_courses))
    checks = 0
    while remaining:
        ready = []
        for course in sorted(remaining):
            ok = True
            for p in sorted(prereqs[course]):
                checks += 1
                if p not in taken:
                    ok = False
                    break
            if ok:
                ready.append(course)
        if not ready:
            return checks
        taken.update(ready)
        remaining -= set(ready)
    return checks

for n in [4, 8, 16]:
    pairs = [(i, i - 1) for i in range(1, n)]
    visits, edges = counted(n, pairs)
    print("chain of", n, "- colour visits:", visits, "- edge reads:", edges, "- brute checks:", brute_checks(n, pairs))

On a chain, the colour search reads each edge exactly once. The sweeping brute force retests the same prerequisites sweep after sweep, and its check count grows far faster. At 16 courses the counts are 15 edge reads against 135 checks.

Edge cases and pitfalls

Zero courses finish trivially. The loops never run, and the answer is True. One course with no pairs is the same story at the smallest real size.

A course that requires itself is the smallest possible cycle. Its own edge points back at a grey course, namely itself. Duplicate pairs, by contrast, are harmless, because the second identical edge reads a black course and is skipped.

def can_finish(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
    for v in graph:
        graph[v] = sorted(graph[v])
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {i: WHITE for i in range(num_courses)}

    def dfs(node):
        colour[node] = GREY
        for nb in graph[node]:
            if colour[nb] == GREY:
                return False
            if colour[nb] == WHITE:
                if not dfs(nb):
                    return False
        colour[node] = BLACK
        return True

    for v in range(num_courses):
        if colour[v] == WHITE:
            if not dfs(v):
                return False
    return True

print("zero courses:", can_finish(0, []))
print("self prerequisite:", can_finish(1, [(0, 0)]))
print("duplicate pairs:", can_finish(2, [(1, 0), (1, 0)]))
print("one clean part and one loop:", can_finish(4, [(1, 0), (3, 2), (2, 3)]))

The mixed plan fails even though half of it is clean. One cycle anywhere makes the full plan impossible, because the loop courses can never be taken. The search reports that with a single grey hit.