TechPrep
Search spaces and optimisationReadLabPracticeCheck

Topological sort

Order the nodes of a dependency graph so every edge points forward, and detect cycles for free.

Course Schedule II. There are n courses. prereqs[i] = [a, b] means you must take b before a. Return an order to take all courses, or [] if it is impossible.

Signals that point here

The idea

Kahn's algorithm: repeatedly take a node with no remaining prerequisites (in-degree 0), output it, and remove its outgoing edges. If you run out of such nodes before outputting all n, the rest sit on a cycle.

The alternative is DFS post-order (reverse the finish order, with a three-colour visited state to catch back edges). Kahn's is easier to get right under pressure and gives cycle detection directly; mention both.

from collections import deque

def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
    indegree = [0] * n
    after: list[list[int]] = [[] for _ in range(n)]
    for course, before in prereqs:
        after[before].append(course)
        indegree[course] += 1
    queue = deque(c for c in range(n) if indegree[c] == 0)
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nxt in after[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == n else []   # short = cycle

Complexity

O(V + E) time and space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: course_order(6, [[1, 0], [2, 0], [3, 1], [3, 2], [4, 3], [5, 4], [5, 2]])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Given a sorted list of words in an unknown alphabet, return a valid letter order.
  2. Return the minimum number of semesters to finish all courses if any number can be taken at once.
  3. Detect a cycle in a directed graph using DFS colours instead of in-degrees.

Check yourself

How does Kahn's algorithm detect a cycle?

Fewer than n nodes are output: the remainder never reach in-degree 0.

What is the cost?

O(V + E).

Saved in this browser.