1 questions using this pattern
Order vertices in a directed acyclic graph (DAG) such that for every edge u -> v, vertex u comes before v in the ordering.
Imagine getting dressed: you must put on underwear before pants, socks before shoes. Topological sort finds a valid order that respects all "must come before" rules. If there's a cycle (shirt requires jacket, jacket requires shirt), no valid order exists.
Two main approaches:
Kahn's Algorithm (BFS): Start with nodes having no incoming edges (in-degree 0). Process them, remove their edges, repeat. If all nodes processed, valid order exists.
DFS-based: Do DFS, add nodes to result when backtracking (post-order). Reverse at end. Cycle exists if we revisit a node in current path.
Use this skeleton as a starting point for problems using this pattern:
from collections import deque
def topological_sort_bfs(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""Kahn's algorithm - returns empty list if cycle exists."""
# Build adjacency list and in-degree count
graph = [[] for _ in range(n)]
in_degree = [0] * n
for u, v in edges: # u -> v (u must come before v)
graph[u].append(v)
in_degree[v] += 1
# Start with nodes having no prerequisites
queue = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If we processed all nodes, valid topological order exists
return result if len(result) == n else []Look for these keywords and patterns in problem descriptions:
Assuming input is always a valid DAG. Must check if all nodes were processed (BFS) or if back-edge exists (DFS).
Fix:
BFS: Check len(result) == n. DFS: Track "visiting" state separately
from "visited."
Confusing "A depends on B" vs "A must come before B." These are opposite edge directions.
Fix:
Clarify: If A depends on B, edge is B -> A (B comes before A).
Return true/false if valid ordering exists
Examples: course-schedule
Return the actual ordering
Examples: course-schedule-ii
Infer ordering from sorted alien words
Examples: alien-dictionary
Test your mastery with complex variations.
Learn these patterns first:
Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.
Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.
Explore similar techniques:
Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.
Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.