Topological Sort

Use Cases

Use Case	Description	Example
Topological Sorting of a Directed Acyclic Graph (DAG)	Given a directed acyclic graph, return a linear ordering of its vertices such that for every directed edge u to v , vertex u comes before vertex v.	For the graph with edges: A → B, A → C, B → D, C → D, one possible result is [A, B, C, D].
Course Scheduling	Given a list of courses and their prerequisites, determine an order to take the courses.	For courses: `{0: [], 1: [0], 2: [1]}`, a valid order could be [0, 1, 2].

Code Template

Initialize indegree and nodes

indegree = defaultdict(int): Stores the indegree (number of incoming edges) for each node. It defaults unseen nodes to 0.
nodes = set(graph): Starts with every node that appears as a graph key. Later, we also add neighbor-only nodes so the template works when a node has incoming edges but no outgoing edges.

Calculate node indegree

The outer loop goes through each node in the graph. The inner loop processes each nei reachable from the current node.
nodes.add(nei) keeps nodes that only appear as neighbors.
indegree[nei] += 1 counts one incoming edge into nei.

Initialize zero-indegree queue

queue = deque([...]) is created after indegrees are counted. It starts with all nodes that have no prerequisites.
result = [] stores the topological order as nodes become ready.

Process ready nodes

while queue: continues as long as there are nodes ready to process.
node = queue.popleft() removes a zero-indegree node.
result.append(node) records it in the topological order.

Update neighbor indegrees

for nei in graph.get(node, []): visits each outgoing neighbor. get handles sink nodes that are not keys in the graph.
indegree[nei] -= 1 removes the processed incoming edge from node.
if indegree[nei] == 0: means all prerequisites for nei have been processed, so it can enter the queue.

Detect cycle

If every node is processed, result is a valid topological order.
If len(result) != len(nodes), some nodes never reached indegree 0, which means the graph has a cycle.

def topological_sort(graph):
    indegree = defaultdict(int)
    nodes = set(graph)

Common mistakes

Missing Nodes That Only Appear as Neighbors

# Wrong: only graph keys are counted
nodes = set(graph)

# Correct:
nodes = set(graph)
for node in graph:
    for nei in graph[node]:
        nodes.add(nei)
        indegree[nei] += 1

Reversing Edge Direction in Course Schedule

# Wrong for prerequisites [course, prereq]
graph[course].append(prereq)
indegree[prereq] += 1

# Correct: prereq must come before course
graph[prereq].append(course)
indegree[course] += 1

Issues and consideration

Ensure that the input graph is a valid directed acyclic graph (DAG). Topological sorting is only applicable to DAGs.
If the graph has cycles, the algorithm will not produce a valid topological sort. You might want to check if the length of the result is equal to the number of nodes in the graph after processing. If not, it indicates a cycle.

210. Course Schedule II

class Solution:
    def findOrder(self, numCourses, prerequisites):
        # Same template: graph + indegree, but nodes are 0 .. numCourses - 1
        graph = defaultdict(list)
        indegree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque([node for node in range(numCourses) if indegree[node] == 0])
        result = []

        while queue:
            node = queue.popleft()
            result.append(node)
            for nei in graph.get(node, []):
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return result if len(result) == numCourses else []

444. Sequence Reconstruction

class Solution:
    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
        # Same template, plus one problem-specific check:
        # at every step, there must be exactly one zero-indegree node.
        graph = defaultdict(set)
        indegree = defaultdict(int)
        nodes = set()

        for seq in seqs:
            nodes.update(seq)

        if set(org) != nodes:
            return False

        for seq in seqs:
            for i in range(len(seq) - 1):
                node, nei = seq[i], seq[i + 1]
                if nei not in graph[node]:
                    graph[node].add(nei)
                    indegree[nei] += 1

        queue = deque([node for node in nodes if indegree[node] == 0])
        result = []

        while queue:
            if len(queue) > 1:
                return False

            node = queue.popleft()
            result.append(node)

            for nei in graph.get(node, []):
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return result == org

1136. Parallel Courses

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        # Same template, but process queue level-by-level.
        # Each BFS level is one semester.
        graph = defaultdict(list)
        indegree = [0] * (n + 1)

        for prev, course in relations:
            graph[prev].append(course)
            indegree[course] += 1

        queue = deque([node for node in range(1, n + 1) if indegree[node] == 0])
        semester = 0
        count = 0

        while queue:
            semester += 1
            level_size = len(queue)

            for _ in range(level_size):
                node = queue.popleft()
                count += 1
                for nei in graph.get(node, []):
                    indegree[nei] -= 1
                    if indegree[nei] == 0:
                        queue.append(nei)

        return semester if count == n else -1

Topological Sort

Use Cases

Code Template

Initialize indegree and nodes

Calculate node indegree

Initialize zero-indegree queue

Process ready nodes

Update neighbor indegrees

Detect cycle

Common mistakes

Issues and consideration

Related Problem