Topological Sort and Cycle Detection
Before you can get dressed, you put on socks before shoes. Before a build system compiles your project, it compiles the files you depend on first. Topological sort answers exactly this question in code: "in what order must these tasks run, given their dependencies?" It only makes sense for graphs with no cycles, so cycle detection and topological sort are really two names for the same idea.
What makes an order possible at all
A DAG (Directed Acyclic Graph) is a directed graph with no cycles: you can never start at a node, follow edges, and arrive back where you started. That property is exactly what makes a valid ordering possible. If task A must come before task B (an edge A→B), a cycle A→B→A would make "before" meaningless, since A would need to come before B and after B at the same time. No valid order could exist.
Topological order: a line-up of nodes such that for every directed edge u → v, u appears before v in the line. A DAG can have more than one valid topological order, or exactly one if it happens to be a strict chain.
# Example: 5 depends on 2 and 0; 4 depends on 0 and 1; 3 depends on 1
# edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
# Valid orders include: [5, 4, 2, 3, 1, 0] and [4, 5, 2, 3, 1, 0]Key fact: a graph has a valid topological order if and only if it is a DAG. So "can this be topologically sorted?" and "does this graph have a cycle?" are the same question asked two ways, which is why cycle detection and topological sort share one algorithm.
Remember: a topological order exists only if the graph has no cycles. Asking "is it a DAG?" and "can it be sorted?" are the same question.
Kahn's algorithm: peel off nodes with nothing left owed to them
Kahn's algorithm repeatedly removes nodes with in-degree 0, meaning no remaining dependencies point at them. That's the whole idea: a node with in-degree 0 can safely run right now, since nothing is still waiting to happen before it.
from collections import deque, defaultdict
def kahn_topo_sort(num_nodes: int, edges: list[tuple[int, int]]) -> list[int]:
graph = defaultdict(list)
in_degree = [0] * num_nodes
for u, v in edges: # u must come before v
graph[u].append(v)
in_degree[v] += 1
queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) != num_nodes:
return [] # cycle detected — not all nodes could be processed
return orderComplexity: Time O(V + E), space O(V + E).
Why it doubles as cycle detection: if the graph has a cycle, the nodes inside that cycle never reach in-degree 0, since each one depends on another node that's also stuck in the cycle. So order ends up shorter than num_nodes. That length check IS the cycle check; no separate logic needed.
Remember: repeatedly peel off nodes with in-degree 0. If the final order is shorter than the node count, a cycle ate the rest.
The DFS alternative
Run DFS from every unvisited node, and when a node's DFS call finishes, meaning every one of its descendants is fully processed, push that node onto a stack. Reverse the stack at the end.
def dfs_topo_sort(num_nodes: int, edges: list[tuple[int, int]]) -> list[int]:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
visited = set()
stack = []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
stack.append(node) # postorder: node goes on stack after all descendants
for node in range(num_nodes):
if node not in visited:
dfs(node)
return stack[::-1]Why postorder + reverse works: a node is only pushed after everything it depends on downstream has already been pushed. Reversing puts dependencies before the things that depend on them. This variant needs a separate 3-color cycle check, covered next, because a plain visited set alone can't tell "currently on this DFS path" apart from "already fully processed."
Trade-off: Kahn's is iterative, so it carries no recursion-depth risk, and it detects cycles for free via the length check. DFS-based is often shorter to write when you already have DFS cycle detection in place, and it fits naturally when the problem is phrased as "process a node only after its dependents," as in course-scheduling frameworks.
Remember: DFS-based topo sort pushes a node onto a stack only after all its descendants are done, then reverses. That reversal is the whole trick.
Detecting a cycle correctly
For an undirected graph, a plain visited set is enough. If you reach an already-visited neighbor that isn't your immediate parent, that's a cycle.
For a directed graph, the interview-relevant case (Course Schedule and friends), you need three states, not two, because a node can be "visited" from a completed branch without being part of any cycle:
WHITE, GRAY, BLACK = 0, 1, 2 # unvisited, in-progress (on current DFS path), done
def has_cycle_directed(num_nodes: int, edges: list[tuple[int, int]]) -> bool:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
color = [WHITE] * num_nodes
def dfs(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # back edge -> cycle
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK
return False
return any(color[n] == WHITE and dfs(n) for n in range(num_nodes))Pitfall: using a single visited set (two states) on a directed graph gives false positives. Two different branches can both reach the same node without a cycle existing at all, since directed edges don't imply "coming back." The GRAY state, tracking the current recursion path specifically, is what correctly identifies a true back edge.
Remember: directed-graph cycle detection needs three states (white/gray/black), not two. GRAY means "on my current path right now," which is the only thing a true cycle can hit.
Course Schedule
LeetCode 207, Topological sort, Detect cycle
"Can you finish all courses?" is exactly "is this prerequisite graph a DAG?" Build the graph, run Kahn's algorithm, and check whether every course got processed.
Approach: Build the adjacency list and in-degree array from the prerequisites, then run Kahn's algorithm; compare the processed count to numCourses.
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return processed == numCoursesComplexity: Time O(V + E), space O(V + E).
Common mistakes: Flipping the edge direction; it runs prereq to course, not course to prereq. Forgetting that courses with zero prerequisites and zero dependents still count toward processed.
Remember: this is topological sort wearing a boolean costume. Just check whether Kahn's algorithm processed every course.
Course Schedule II
LeetCode 210, Topological sort, Return order
Identical to Course Schedule I, but instead of a true/false answer, you return the actual valid order (or an empty list if it's impossible).
Approach: Reuse Kahn's algorithm verbatim, but collect the order instead of only counting it.
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else []Complexity: Time O(V + E), space O(V + E).
Common mistakes: Returning a partial order instead of an empty list when a cycle exists. Always check the length before returning.
Remember: same algorithm as Course Schedule I, just return the collected order instead of a boolean.
Alien Dictionary
LeetCode 269, Topological sort, Hard
You're given a list of words already sorted according to some unknown alien alphabet. Comparing adjacent words reveals relative character ordering: the first character where two consecutive words differ tells you "this letter comes before that letter." Build a graph of those constraints and topologically sort the alphabet's letters.
Approach: For each pair of adjacent words, find the first index where the characters differ; that gives one directed edge word1[i] -> word2[i]. Special case: if word1 is longer than word2 but word2 is exactly its prefix, such as "abc" before "ab", the order is invalid and you return "". Then run Kahn's algorithm over the 26 letters.
def alienOrder(words: list[str]) -> str:
graph = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for w1, w2 in zip(words, words[1:]):
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return "" # invalid: longer word can't be a prefix of the next
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in graph[c1]:
graph[c1].add(c2)
in_degree[c2] += 1
break # only the first differing pair gives a constraint
queue = deque(c for c in in_degree if in_degree[c] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for neighbor in graph[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return "".join(order) if len(order) == len(in_degree) else ""Complexity: Time O(C), where C is the total character count across all words: each adjacent-pair comparison is bounded by word length, and the topological sort itself is O(26) for nodes and edges. Space is O(1) in practice, since there are at most 26 letters.
Common mistakes: Not handling the "prefix but longer" invalid case. Adding duplicate edges when the same letter pair appears across multiple word comparisons; the "already in graph" guard prevents inflating in-degree counts. Continuing the inner loop past the first differing character, since later differences carry no information once the first one is found.
Remember: compare only adjacent words, take only the FIRST differing character per pair, and watch for the "longer word is a prefix of the shorter one" invalid case.
Longest Increasing Path in a Matrix
LeetCode 329, DFS + Memoization
Treat each cell as a graph node with a directed edge to any 4-directional neighbor holding a strictly greater value. Since values strictly increase along any path, this graph is automatically acyclic, no separate cycle check needed. Find the longest path in this implicit DAG with DFS plus memoization; it's topological-DAG-style DP even though you never build an explicit adjacency list.
Approach: DFS from each cell, caching "longest increasing path starting here" so overlapping subproblems are never recomputed.
def longestIncreasingPath(matrix: list[list[int]]) -> int:
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
memo = {}
def dfs(r, c):
if (r, c) in memo:
return memo[(r, c)]
best = 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[(r, c)] = best
return best
return max(dfs(r, c) for r in range(rows) for c in range(cols))Complexity: Time O(rows × cols), since memoization computes each cell's answer exactly once. Space O(rows × cols) for the memo and recursion stack.
Common mistakes: Trying to solve this with a visited set instead of memoization. A visited set assumes you never revisit a cell in any path, but here you legitimately want to revisit cells from different starting points. "Longest path starting at (r, c)," cached, is the correct DP framing.
Remember: strictly increasing values make the implicit graph automatically acyclic. Cache "best path starting here" instead of using a visited set.