Topological Sort & Union-Find

Step by step

• Node being output
• Ready queue (in-degree 0)
• Already in the order
• Stuck on a cycle

Press Start or Step: the step the animation is on lights up below.

1. 1

   Count each node's incoming edges

   One pass over the edges gives every node's in-degree. Nodes at 0 have no prerequisites and start in the ready queue.

   for (u, v) in edges: indeg[v] += 1; ready = [v with indeg 0]
2. 2

   Output a ready node

   Take a node from the ready queue and append it to the order. Everything it depends on is already in the output.

   u = ready.popleft(); order.append(u)
3. 3

   Remove its edges → counts drop

   Each outgoing edge was one prerequisite of its target, and that prerequisite is now met. Lower the target's count.

   for v in out[u]: indeg[v] -= 1
4. 4

   Count hits 0 → node is ready

   A node whose last prerequisite was just met joins the ready queue.

   if indeg[v] == 0: ready.append(v)
5. 5

   Queue empty → order complete

   Every node was output, so the order respects every edge.

   return order # len(order) == n
6. 6

   Nodes left over → there's a cycle

   The queue ran dry with nodes still waiting. They depend on each other in a loop, so no valid order exists.

   if len(order) < n: return None # cycle