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.
"""
successors: list[list[int]] = [[] for _ in range(n)]
indegree = [0] * n
for before, after in edges:
successors[before].append(after)
indegree[after] += 1
queue = deque(node for node in range(n) if indegree[node] == 0)
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in successors[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0: # its last prerequisite just cleared
queue.append(nxt)
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.
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."""
successors: list[list[int]] = [[] for _ in range(n)]
for before, after in edges:
successors[before].append(after)
colour = [WHITE] * n
order: list[int] = []
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
for nxt in successors[node]:
if not visit(nxt):
return False
colour[node] = BLACK
order.append(node) # post-order: after all descendants
return True
for node in range(n):
if not visit(node):
return []
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.
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."""
successors: list[list[int]] = [[] for _ in range(n)]
indegree = [0] * n
for before, after in edges:
successors[before].append(after)
indegree[after] += 1
ready = [node for node in range(n) if indegree[node] == 0]
heapq.heapify(ready)
order: list[int] = []
while ready:
node = heapq.heappop(ready) # always the smallest available node
order.append(node)
for nxt in successors[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
heapq.heappush(ready, nxt)
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).
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: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, needs in prerequisites:
# Edge runs from the prerequisite to the course it unlocks.
unlocks[needs].append(course)
indegree[course] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
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.
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: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, needs in prerequisites:
unlocks[needs].append(course)
indegree[course] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
taken = 0
semesters = 0
while queue:
for _ in range(len(queue)): # one semester's worth of courses
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
semesters += 1
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: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, needs in prerequisites:
unlocks[needs].append(course)
indegree[course] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
order: list[int] = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
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.
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'
"""
successors: defaultdict[str, set[str]] = defaultdict(set)
# Every letter that appears must show up in the answer, even with no edges.
indegree: dict[str, int] = {ch: 0 for word in words for ch in word}
for first, second in zip(words, words[1:]):
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
break
else:
# No difference within the shared length. A longer word may not
# come before its own prefix.
if len(first) > len(second):
return ""
queue = deque(ch for ch in indegree if indegree[ch] == 0)
order: list[str] = []
while queue:
ch = queue.popleft()
order.append(ch)
for nxt in successors[ch]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
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.
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.