#207MediumGraphs

Course Schedule

The tell: Prerequisites — a directed graph where the question is really 'is it acyclic?'

How you get there

1Build the graph and count incoming edges per node.
2Repeatedly remove any node with no remaining prerequisites (Kahn's algorithm).
3If fewer than n nodes are removed, a cycle blocked the rest.

Solution

Python

from collections import deque

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    done = 0
    while queue:
        node = queue.popleft()
        done += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    return done == num_courses

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

What goes wrong

Reversing the edge direction inverts the whole problem — check which element is the prerequisite.

Test yourself on DSA Next: Number of Connected Components in an Undirected Graph →