• V = number of vertices, E = number of edges
• The graph must be directed — an ordering is meaningless on undirected edges
• The graph must be acyclic for an ordering to exist
• A cycle must be detected and reported, not silently ignored
• Runs in O(V + E) time and O(V) space

Take the statement literally and ask what it demands. Every edge u → v is a constraint saying "u must come before v", and you are asked to lay all the vertices out on a line so that no constraint is broken. Nothing about distance, nothing about counting — a pure ordering problem.

Before building anything, settle when the answer exists, because that determines the shape of the algorithm.

Suppose the graph contains a cycle: A → B → C → A. The first edge demands A before B, the second B before C, the third C before A. Chaining them, A must come before A, which no ordering on a line can satisfy. So a cycle makes the task impossible, and one cycle anywhere in the graph is enough.

The converse is also true — every acyclic directed graph has at least one valid ordering — and the argument is short and worth knowing. In a finite graph with no cycles there must be some vertex with no incoming edges. If every vertex had one, you could walk backwards forever, and with finitely many vertices such a walk must eventually repeat one, which is a cycle. So a vertex with no incoming edges exists; put it first, delete it, and the remainder is still acyclic, so repeat. The process places every vertex.

That proof is not decoration — it is the first algorithm, transcribed.

Give each vertex an in-degree: the number of edges pointing into it, meaning the number of constraints still blocking it. A vertex with in-degree 0 has nothing that must precede it, so it is safe to output right now.

Output such a vertex, then delete it — and deleting a vertex means every vertex it pointed to loses one blocker, so decrement their in-degrees. Any that reach 0 have just become free, and join the pool of available vertices. Repeat until the pool is empty.

from collections import deque

def topo_sort_kahn(V, adj):
    in_degree = [0] * V
    for u in range(V):
        for v in adj[u]:
            in_degree[v] += 1                  # count blockers

    queue = deque(u for u in range(V) if in_degree[u] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1                  # u is placed; v loses a blocker
            if in_degree[v] == 0:
                queue.append(v)                # v is now free

    return order if len(order) == V else []    # short output means a cycle

The cycle check at the end is the elegant part, and it deserves an argument rather than a rule. If the loop ends with vertices left unplaced, every one of them still has in-degree above 0, meaning each has a blocker that was itself never placed. Follow those blockers backwards from any unplaced vertex: each step lands on another unplaced vertex, and since there are finitely many, the walk must eventually revisit one — which is a cycle. So a short output is not merely a symptom of a cycle, it is a proof of one.

The cost: building in-degrees scans every edge once, and the main loop pops each vertex once and scans its neighbour list once. O(V + E) time, O(V) space.

Note that the queue could be any container — a stack works identically, and produces a different but equally valid ordering. The FIFO discipline is not load-bearing here, unlike in shortest-path BFS. If you specifically want the lexicographically smallest ordering, swap in a min-heap and pay O(V log V).

There is a second approach that comes at the problem from the far end, and it is shorter to write once understood.

Run a depth-first search. When you enter a vertex, recurse into all of its out-neighbours first, and only after every one of them has completely finished do you append the vertex to a list. This is a post-order append — the vertex is recorded on the way out, not on the way in.

Then reverse the list.

def topo_sort_dfs(V, adj):
    visited = [False] * V
    order = []

    def visit(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                visit(v)
        order.append(u)             # appended only after ALL descendants are done

    for u in range(V):
        if not visited[u]:
            visit(u)

    return order[::-1]

Why does reversing post-order give a valid topological order? Take any edge u → v and show u ends up before v in the reversed list, which is the same as showing v finishes before u in the original.

Two cases cover it. When visit(u) examines the edge to v, either v has not been visited, in which case visit(u) calls visit(v) directly and waits for it to return — so v finishes first. Or v has already been visited, and since the graph is acyclic, v cannot still be in progress on the current recursion path (that would mean a route from v back to u, plus the edge u → v, forming a cycle). So v has already finished. Either way v finishes before u, for every edge. Reversing finish order therefore respects every edge.

Edges: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1.

Kahn's. In-degrees: node 0 is pointed at by 5 and 4, so 2. Node 1 is pointed at by 4 and 3, so 2. Node 2 is pointed at by 5, so 1. Node 3 is pointed at by 2, so 1. Nodes 4 and 5 have none, so 0.

Six vertices placed out of six, so no cycle. Check a constraint at random: the edge 2→3 requires 2 before 3, and 2 sits at index 2 while 3 sits at index 4. Every other edge checks out likewise.

DFS from node 0 upward. visit(0) finds no out-edges and appends 0 immediately, so order = [0]. visit(1) likewise appends: [0, 1]. visit(2) recurses into 3, which recurses into 1 — already visited — so 3 appends, then 2 appends: [0, 1, 3, 2]. visit(3) is skipped, already visited. visit(4) finds 0 and 1 both visited, so appends: [0, 1, 3, 2, 4]. visit(5) finds 2 and 0 visited, appends: [0, 1, 3, 2, 4, 5].

Reversed: 5, 4, 2, 3, 1, 0. A different ordering from Kahn's, and equally valid — check 2→3 again: 2 at index 2, 3 at index 3.

Recognition signals are unusually clean here. Any statement about dependencies, prerequisites, build order, task scheduling with "must happen before", or resolving what to install first is a topological sort. The giveaway phrasing is "A requires B" or "A must come before B" together with a request for an order or for whether an order exists.

The pairing with cycle detection is the thing to remember: a valid ordering exists exactly when no cycle exists, so these are two views of one question. Course Schedule asks only whether the ordering exists and returns a boolean; Course Schedule II asks for the ordering itself. The same code answers both — one returns len(order) == V, the other returns order.

Train the reflex: when a problem gives you constraints of the form "this before that" and asks for a sequence, build the directed graph, count in-degrees, and peel off what is unblocked. If you cannot peel everything, the constraints contradict each other.