Interviewer cue: “in what order should these tasks/courses/builds run, given these dependencies” is a topological sort problem. A topological order of a directed acyclic graph (DAG) is a linear arrangement of its nodes such that for every directed edge u -> vu -> v, uu comes before vv in the ordering. It only exists when the graph has no cycles — if uu transitively depends on itself, there’s no valid order at all.

What you’ll learn

• What a DAG is, and why a topological order only exists when there’s no cycle.
• Kahn’s algorithm: a BFS driven by in-degree counts, which also detects cycles for free.
• DFS-based topological sort: post-order traversal, reversed.
• Why reversed post-order is a valid topological order in the first place.
• Real applications: build/dependency ordering and course scheduling.

A DAG and one of its valid orderings

  graph LR
    N0["A"] --> N1["B"]
    N0 --> N2["C"]
    N1 --> N3["D"]
    N2 --> N3
    N3 --> N4["E"]

A, B, C, D, EA, B, C, D, E is a valid order here (so is A, C, B, D, EA, C, B, D, E — ties between independent nodes can go either way). What’s not valid is anything placing DD before BB or CC, since both edges point into DD.

Kahn’s algorithm: BFS driven by in-degree

Track each node’s in-degree (how many edges point into it). Any node with in-degree 00 has no unfinished prerequisites, so it’s safe to process right now. Processing a node “removes” its outgoing edges, which may drop a neighbor’s in-degree to 00 and unlock it next.

from collections import deque, defaultdict
 
 
def topological_sort_kahn(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
 
    for u, v in edges:            # edge u -> v means "u must come before v"
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque(node for node in range(n) if in_degree[node] == 0)   # no prerequisites left
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:   # every prerequisite of neighbor is now satisfied
                queue.append(neighbor)
 
    if len(order) != n:
        return None   # fewer nodes processed than exist -> a cycle blocked the rest
 
    return order
 
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("topological order:", topological_sort_kahn(5, edges))
 
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print("cyclic graph result:", topological_sort_kahn(3, cyclic_edges))

from collections import deque, defaultdict
 
 
def topological_sort_kahn(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
 
    for u, v in edges:            # edge u -> v means "u must come before v"
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque(node for node in range(n) if in_degree[node] == 0)   # no prerequisites left
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:   # every prerequisite of neighbor is now satisfied
                queue.append(neighbor)
 
    if len(order) != n:
        return None   # fewer nodes processed than exist -> a cycle blocked the rest
 
    return order
 
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("topological order:", topological_sort_kahn(5, edges))
 
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print("cyclic graph result:", topological_sort_kahn(3, cyclic_edges))

DFS-based topological sort: post-order, reversed

This reuses the exact 3-state (WHITEWHITE / GRAYGRAY / BLACKBLACK) cycle-detection trick from Depth First Search: run a DFS from every unvisited node, and append a node to the order only after every one of its neighbors has been fully explored. Reversing that list at the end gives a valid topological order.

def topological_sort_dfs(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
 
    WHITE, GRAY, BLACK = 0, 1, 2   # unvisited, currently exploring, fully done
    state = [WHITE] * n
    order = []
 
    def dfs(node):
        state[node] = GRAY
        for neighbor in graph[node]:
            if state[neighbor] == GRAY:
                return False   # back edge to a node still on the path -> cycle
            if state[neighbor] == WHITE and not dfs(neighbor):
                return False
        state[node] = BLACK
        order.append(node)   # append AFTER every descendant is fully processed
        return True
 
    for node in range(n):
        if state[node] == WHITE:
            if not dfs(node):
                return None
 
    return order[::-1]   # reverse post-order = topological order
 
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("topological order (DFS):", topological_sort_dfs(5, edges))
 
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print("cyclic graph result (DFS):", topological_sort_dfs(3, cyclic_edges))

def topological_sort_dfs(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
 
    WHITE, GRAY, BLACK = 0, 1, 2   # unvisited, currently exploring, fully done
    state = [WHITE] * n
    order = []
 
    def dfs(node):
        state[node] = GRAY
        for neighbor in graph[node]:
            if state[neighbor] == GRAY:
                return False   # back edge to a node still on the path -> cycle
            if state[neighbor] == WHITE and not dfs(neighbor):
                return False
        state[node] = BLACK
        order.append(node)   # append AFTER every descendant is fully processed
        return True
 
    for node in range(n):
        if state[node] == WHITE:
            if not dfs(node):
                return None
 
    return order[::-1]   # reverse post-order = topological order
 
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("topological order (DFS):", topological_sort_dfs(5, edges))
 
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print("cyclic graph result (DFS):", topological_sort_dfs(3, cyclic_edges))

Why reversed post-order works

A node is only appended to orderorder once every node reachable from it has already been appended — so in the raw orderorder list, every node’s descendants appear before it. Reversing the list flips that, so every node’s descendants appear after it, and every dependency appears before the thing that depends on it. That’s exactly the topological property.

  graph LR
    N0["post-order: D, B, C, A, E"] --> N1["reversed: E, A, C, B, D"]

Applications: build systems and course scheduling

• Build/dependency ordering: a package manager or build tool models “package A requires package B” as an edge B -> AB -> A, then topologically sorts to decide install/compile order. A cycle here means two packages depend on each other — an unresolvable dependency loop.
• Course scheduling: “course B requires course A” becomes edge A -> BA -> B. Course Schedule asks if a valid order exists (equivalent to “no cycle”); Course Schedule II asks you to actually produce that order.
• Task scheduling with prerequisites in general — spreadsheet cell recalculation order, compiler instruction scheduling, and Makefile target ordering all reduce to the same problem.

Complexity

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 207 — Course Schedule · Medium

Problem. Given numCoursesnumCourses and prerequisite pairs [course, prereq][course, prereq], return TrueTrue if all courses can be finished.

Constraints. 1 <= numCourses <= 20001 <= numCourses <= 2000, 0 <= len(prerequisites) <= 50000 <= len(prerequisites) <= 5000, no duplicate pairs.

Examples. 2, [[1,0]]2, [[1,0]] gives TrueTrue · 2, [[1,0],[0,1]]2, [[1,0],[0,1]] gives FalseFalse

LC 210 — Course Schedule II · Medium

Problem. Return any valid order in which to take all courses, or an empty array if impossible.

Constraints. 1 <= numCourses <= 20001 <= numCourses <= 2000, 0 <= len(prerequisites) <= 50000 <= len(prerequisites) <= 5000.

Examples. 4, [[1,0],[2,0],[3,1],[3,2]]4, [[1,0],[2,0],[3,1],[3,2]] gives [0,1,2,3][0,1,2,3] or [0,2,1,3][0,2,1,3] · 2, [[1,0],[0,1]]2, [[1,0],[0,1]] gives [][]

LC 310 — Minimum Height Trees · Medium

Problem. Given a tree with nn nodes, return all root labels that produce a minimum-height rooted tree.

Constraints. 1 <= n <= 2 * 10^41 <= n <= 2 * 10^4, edgesedges forms a tree.

Examples. n = 4, edges = [[1,0],[1,2],[1,3]]n = 4, edges = [[1,0],[1,2],[1,3]] gives [1][1] · n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] gives [3,4][3,4]

LeetCode problem set

Recap

• A topological order only exists for a DAG — a directed graph with no cycles.
• Kahn’s algorithm: BFS seeded with every in-degree-0 node; a cycle reveals itself as len(order) != nlen(order) != n.
• DFS-based: append each node to orderorder after all its descendants are done, then reverse; a cycle reveals itself as a GRAYGRAY back edge.
• Both run in $O(V + E)$ time and both double as cycle detectors — pick whichever fits the surrounding code (BFS-style queue vs. recursive DFS).

Next up in Phase 7: shortest-path algorithms (Dijkstra, Bellman-Ford) that build directly on the weighted-graph representations, DSU, and traversal patterns covered so far.