Order a set of tasks so every task comes after the things it depends on. The same algorithm that produces the order also tells you when no order exists.
Anything phrased as “X must happen before Y” is a directed graph, and the question is almost always one of two: give me a valid order, or is a valid order even possible. Both are answered by the same twenty lines, and the second falls out of the first for free.
| Signal | What it looks like |
|---|---|
| Prerequisites | “you must take A before B”, “task X depends on Y”. |
| Build or install order | Package managers, build systems, migration scripts, spreadsheet recalculation. |
| Deducing an alphabet | “given sorted words in an unknown language, recover the letter order”. |
| Feasibility | “can all tasks be completed” is really “is the graph acyclic”. |
| Layered scheduling | “minimum number of semesters” is the number of BFS rounds. |
[a, b] meaning “to take a you must first take b” is an edge from b to a, and it raises the in-degree of a. Reversing this is the single most common way to fail these problems, and the reversed version still produces a plausible-looking answer on symmetric test cases. Read the statement twice and write one example edge on the board.len(order) == n is a complete cycle test, and it costs one comparison.That is why “can you finish all courses” and “give me the order” are the same function with a different return statement.
| Kahn, BFS with in-degrees | DFS with post-order | |
|---|---|---|
| Produces | The order directly | The reverse order; you must flip it |
| Cycle test | Count the emitted nodes | Three-colour marking: grey means a cycle |
| Gives layers | Yes, one per round, so “minimum semesters” is free | No |
| Recursion depth | None | O(V), which Python can blow |
| Verdict | Prefer this. Easier to explain and to get right. | Know it as the alternative. |
from collections import deque
def topological_order(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""Order n nodes so every edge (before, after) is respected.
Returns an empty list if the graph has a cycle.
"""
# One empty list of successors per node, nodes 0..n-1.
successors: list[list[int]] = [[] for _ in range(n)]
# indegree[node] = how many prerequisites are not done yet. 0 for all at start.
indegree = [0] * n
for before, after in edges:
successors[before].append(after)
indegree[after] += 1 # +1: after waits on one more node
# Seed with every node at indegree 0: nothing blocks them.
queue = deque(node for node in range(n) if indegree[node] == 0)
order: list[int] = []
# Invariant: every node in order, or in the queue, has all its
# prerequisites already placed in order.
while queue:
node = queue.popleft()
order.append(node)
# Placing node clears one prerequisite for each successor.
for nxt in successors[node]:
indegree[nxt] -= 1 # -1: one fewer prerequisite left
if indegree[nxt] == 0: # its last prerequisite just cleared
queue.append(nxt)
# Fewer than n placed means some nodes never reached 0: a cycle.
return order if len(order) == n else []
Decrement then test, in that order, and test for exactly zero. Testing <= 0 would enqueue a node twice on a multi-edge.
# Three node states. 0 = WHITE: not visited yet. 1 = GREY: on the current
# DFS path. 2 = BLACK: finished, all descendants done.
WHITE, GREY, BLACK = 0, 1, 2
def topological_order_dfs(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""Same result via post-order DFS. Grey means we are inside a cycle."""
# One empty list of successors per node, nodes 0..n-1.
successors: list[list[int]] = [[] for _ in range(n)]
for before, after in edges:
successors[before].append(after)
colour = [WHITE] * n # every node starts unvisited
order: list[int] = []
# Returns False if a cycle is reachable from node, else True.
def visit(node: int) -> bool:
if colour[node] == GREY:
return False # back edge: a cycle
if colour[node] == BLACK:
return True # already finished
colour[node] = GREY # node is now on the current path
for nxt in successors[node]:
if not visit(nxt):
return False # pass the cycle signal up
colour[node] = BLACK # all descendants done, leave the path
order.append(node) # post-order: after all descendants
return True
# Start a DFS from every node so disconnected parts are covered.
for node in range(n):
if not visit(node):
return [] # empty list: a cycle, no valid order
order.reverse() # post-order is the reverse topological order
return order
Grey means “on the current path”. Reaching a grey node means the path loops back on itself. Black means “done, and safe to skip”. Two colours are not enough, because you cannot distinguish those two cases.
Reading the figure. Amber nodes are grey, which means they are on the current DFS path. Green is black, meaning the node and all its descendants are done. Neutral is white, not visited yet. On the left, node 2 finishes first, so post-order lists it first. On the right, the red edge from 2 points at a grey node. That back edge is the cycle signal.
import heapq
def smallest_topological_order(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""Kahn's algorithm with a min-heap instead of a queue."""
# One empty list of successors per node, nodes 0..n-1.
successors: list[list[int]] = [[] for _ in range(n)]
indegree = [0] * n # 0: no prerequisites counted yet
for before, after in edges:
successors[before].append(after)
indegree[after] += 1 # +1: after waits on one more node
# Every node at indegree 0 is ready now. heapify makes it a min-heap.
ready = [node for node in range(n) if indegree[node] == 0]
heapq.heapify(ready)
order: list[int] = []
# Invariant: ready holds exactly the unplaced nodes with no blockers left.
while ready:
node = heapq.heappop(ready) # always the smallest available node
order.append(node)
for nxt in successors[node]:
indegree[nxt] -= 1 # -1: one fewer prerequisite left
if indegree[nxt] == 0: # 0: nothing blocks it now
heapq.heappush(ready, nxt)
# Fewer than n placed means a cycle blocked the rest.
return order if len(order) == n else []
One data-structure swap turns any valid order into the smallest one. Cost rises from O(V + E) to O(V log V + E).
Reading the figure. Both runs start with 0 and 1 ready, so the gray cells match. Then 3 and 2 become ready in that order. The deque hands them out in arrival order (amber). The heap hands out the smallest first (green). Both orders are valid. Only the heap gives the smallest one.
indegree <= 0. With duplicate edges that enqueues a node twice. Test for exactly 0.There are num_courses courses labelled 0 to num_courses - 1. Each pair [a, b] means you must take course b before course a. Return True if you can finish all courses.
[a, b] is an edge from b to a. Taking b unlocks a.from collections import deque
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
"""True if every course can be taken, given the prerequisite pairs.
Args:
num_courses: Courses are labelled 0 .. num_courses - 1.
prerequisites: Pairs [a, b] meaning b must be taken before a.
Returns:
True if the prerequisite graph is acyclic.
Example:
>>> can_finish(2, [[1, 0]])
True
>>> can_finish(2, [[1, 0], [0, 1]])
False
"""
# unlocks[c] = courses that list c as a prerequisite.
unlocks: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses # 0: no prerequisites counted yet
for course, needs in prerequisites:
# Edge runs from the prerequisite to the course it unlocks.
unlocks[needs].append(course)
indegree[course] += 1 # +1: course waits on one more
# Start with every course that has 0 prerequisites.
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
taken = 0 # 0: no courses taken yet
# Invariant: taken counts courses whose prerequisites were all taken first.
while queue:
course = queue.popleft()
taken += 1 # +1: one more course done
for nxt in unlocks[course]:
indegree[nxt] -= 1 # -1: one prerequisite of nxt is done
if indegree[nxt] == 0: # 0: nxt is ready to take
queue.append(nxt)
# Anything never emitted is stuck waiting inside a cycle.
return taken == num_courses
num_courses = 2, prerequisites = [[1, 0], [0, 1]]. Course 1 needs 0, and course 0 needs 1. Both in-degrees are 1, so the initial queue is empty, the loop never runs, and taken is 0. Since 0 != 2, the answer is False. The cycle is detected without any explicit cycle-finding code.
Reading the figure. Each arrow points from a prerequisite to the course it unlocks. Both nodes are red because each waits on the other. Neither count can drop to 0. So the queue starts empty and the count of taken courses stays below 2.
V is num_courses and E is the number of prerequisite pairs. Every node is queued once and every edge is relaxed once.
def minimum_semesters(num_courses: int, prerequisites: list[list[int]]) -> int:
"""Fewest terms to finish everything, taking any number of ready courses per term.
Each round of the outer loop is one semester, exactly as in the
level-by-level BFS template.
"""
# unlocks[c] = courses that list c as a prerequisite.
unlocks: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses # 0: no prerequisites counted yet
for course, needs in prerequisites:
unlocks[needs].append(course)
indegree[course] += 1 # +1: course waits on one more
# The first semester is every course with 0 prerequisites.
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
taken = 0 # 0: no courses taken yet
semesters = 0 # 0: no terms used yet
# Invariant: at the top of each pass, the queue holds exactly the
# courses that become ready in the next semester.
while queue:
for _ in range(len(queue)): # one semester's worth of courses
course = queue.popleft()
taken += 1 # +1: one more course done
for nxt in unlocks[course]:
indegree[nxt] -= 1 # -1: one prerequisite of nxt is done
if indegree[nxt] == 0: # 0: ready, so it joins next semester
queue.append(nxt)
semesters += 1 # +1: that semester is over
# -1: some courses sit in a cycle and can never be taken.
return semesters if taken == num_courses else -1
That inner for _ in range(len(queue)) is the level-size trick from Pattern 7, unchanged. The layers of a topological sort are BFS rounds.
True.[0, 0]: in-degree 1 that nothing can clear, so False. Ask whether self-loops can appear.== 0.num_courses = 0: returns True.Same input, but return an actual order in which all courses can be taken. Return an empty list if no order exists.
from collections import deque
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
"""An order in which all courses can be taken, or [] if impossible.
Args:
num_courses: Courses are labelled 0 .. num_courses - 1.
prerequisites: Pairs [a, b] meaning b must be taken before a.
Returns:
A valid ordering, or an empty list when the graph has a cycle.
Example:
>>> find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
[0, 1, 2, 3]
"""
# unlocks[c] = courses that list c as a prerequisite.
unlocks: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses # 0: no prerequisites counted yet
for course, needs in prerequisites:
unlocks[needs].append(course) # edge: prerequisite -> course
indegree[course] += 1 # +1: course waits on one more
# Start with every course that has 0 prerequisites.
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
order: list[int] = []
# Invariant: every course in order came after all its prerequisites.
while queue:
course = queue.popleft()
order.append(course)
for nxt in unlocks[course]:
indegree[nxt] -= 1 # -1: one prerequisite of nxt is done
if indegree[nxt] == 0: # 0: nxt is ready to take
queue.append(nxt)
# A short order means some courses never became available: a cycle.
return order if len(order) == num_courses else []
num_courses = 4, pairs [[1,0],[2,0],[3,1],[3,2]]. Course 0 unlocks 1 and 2, and both of those unlock 3.
| step | emitted | in-degrees after | queue |
|---|---|---|---|
| start | — | [0, 1, 1, 2] | [0] |
| 1 | 0 | [0, 0, 0, 2] | [1, 2] |
| 2 | 1 | [0, 0, 0, 1] | [2] |
| 3 | 2 | [0, 0, 0, 0] | [3] |
| 4 | 3 | — | [] |
Result [0, 1, 2, 3]. Note that [0, 2, 1, 3] is equally valid, and which one you get depends only on the order the queue happens to hold.
Reading the figure. Each box is one step. Green nodes are already in the order. Amber nodes are in the queue. Gray nodes still wait on a prerequisite. The text under each graph shows the in-degree list, the queue, and the order so far. Node 3 needs two decrements, so it turns amber only after both 1 and 2 are emitted.
order, every one of its prerequisites has already been appended. That holds because the course only entered the queue when its in-degree reached zero, and each decrement was performed by a prerequisite at the moment that prerequisite was emitted. Induction on the emissions finishes the proof. Being able to state this in two sentences separates a memorised solution from an understood one.[0, 1, …, n-1], which is valid.[], even if most of the graph is fine.You are given a list of words written in an alien language, sorted according to that language’s letter order. Recover a possible ordering of its letters. Return "" if the input is inconsistent.
Non-adjacent pairs give no extra information. If a < b and b < c, then a < c follows, and the topological sort handles the transitivity. So n - 1 comparisons are enough, not n². Saying that is worth a point on its own.
| Failure | Example | Handling |
|---|---|---|
| Prefix rule violated | ["abc", "ab"] | A longer word cannot precede its own prefix. Return "". |
| Contradictory constraints | ["a", "b", "a"] | Creates a cycle, caught by the length check. |
| Order not fully determined | ["z", "x"] with an unseen letter | Not a failure. Any valid order is accepted. |
from collections import defaultdict, deque
def alien_order(words: list[str]) -> str:
"""Recover a letter ordering consistent with a sorted alien word list.
Args:
words: Words sorted by the unknown alphabet.
Returns:
One valid ordering of every letter that appears, or "" if the
input is contradictory.
Example:
>>> alien_order(["wrt", "wrf", "er", "ett", "rftt"])
'wertf'
"""
# letter -> letters that must come after it. A set blocks duplicate edges.
successors: defaultdict[str, set[str]] = defaultdict(set)
# Every letter that appears must show up in the answer, even with no edges.
# 0: no incoming edges counted yet.
indegree: dict[str, int] = {ch: 0 for word in words for ch in word}
# words[1:] shifts by 1, so zip pairs each word with the next one.
for first, second in zip(words, words[1:]):
# Walk both words side by side. zip stops at the shorter length.
for a, b in zip(first, second):
if a != b:
# The first difference is the only constraint this pair gives.
if b not in successors[a]:
successors[a].add(b) # guard against double counting
indegree[b] += 1 # +1: b waits on one more letter
break
else:
# No difference within the shared length. A longer word may not
# come before its own prefix.
if len(first) > len(second):
return "" # "": the input is contradictory
# Start with every letter that has 0 incoming edges.
queue = deque(ch for ch in indegree if indegree[ch] == 0)
order: list[str] = []
# Invariant: each letter in order comes after every letter that must precede it.
while queue:
ch = queue.popleft()
order.append(ch)
for nxt in successors[ch]:
indegree[nxt] -= 1 # -1: one blocker of nxt is placed
if indegree[nxt] == 0: # 0: nxt is free to place
queue.append(nxt)
# Missing letters were stuck in a cycle, so return "" for no valid order.
return "".join(order) if len(order) == len(indegree) else ""
["wrt", "wrf", "er", "ett", "rftt"]:
| adjacent pair | first difference | edge |
|---|---|---|
| wrt, wrf | t vs f | t → f |
| wrf, er | w vs e | w → e |
| er, ett | r vs t | r → t |
| ett, rftt | e vs r | e → r |
The edges form a single chain w → e → r → t → f, so the order is "wertf" and it is unique here. Notice each pair produced exactly one edge, and everything after the first difference was ignored.
Reading the figure. Each column is one pair of adjacent words. Gray letters match. The amber letters are the first place the words differ, and they give one edge. Dashed letters come after the difference and are ignored. The green chain at the bottom is the topological sort of those four edges.
C is the total number of characters across all words. The graph has at most U nodes and U² edges, where U is the alphabet size, so with a fixed alphabet the space is constant. Quoting it as O(1) with that justification is the sharper answer.
indegree with every letter seen. A letter with no constraints still belongs in the output. Building the node set from the edges alone silently drops it.break after the first difference. Continuing would generate constraints the input does not support.if b not in successors[a] check, the in-degree is inflated and never reaches zero.["abc"]: no pairs, no edges, so any order of a, b, c is valid.["abc", "ab"]: prefix rule violated, returns "".["ab", "abc"]: legal, and yields no edge.n nodes means the rest are stuck in a cycle.Pattern 16, Union-Find, is the other graph structure worth owning. Topological sort answers questions about direction and order. Union-Find answers questions about connectivity, and it does so on a graph that keeps changing.