Middle · Algorithms

Topological order and cycle detection

How do you schedule dependencies and detect when no valid order exists?

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

ALGORITHM LAB · STEP THROUGH THE INVARIANT

Input scenario

[[1, 2], [3], [3], []]

STEP 1 / 6

Count prerequisites

indegree

ready

emitted

∅ Empty

Only zero-indegree vertices can enter the ready queue.

Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

// Caller validates every node ID and bounds graph size.
func TopologicalOrder(adj [][]int) ([]int, bool) {
	degree := make([]int, len(adj))
	for _, edges := range adj {
		for _, v := range edges {
			degree[v]++
		}
	}
	queue := make([]int, 0, len(adj))
	for v, n := range degree {
		if n == 0 {
			queue = append(queue, v)
		}
	}
	order := make([]int, 0, len(adj))
	for head := 0; head < len(queue); head++ {
		u := queue[head]
		order = append(order, u)
		for _, v := range adj[u] {
			degree[v]--
			if degree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(order) != len(adj) {
		return nil, false
	}
	return order, true
}

Reveal a strong answer

For each directed edge u→v, compute the indegree of v. A FIFO queue starts with every zero-indegree vertex. Removing u satisfies one prerequisite for each neighbor; enqueue that neighbor when its indegree becomes zero.
The emitted prefix always respects prerequisites. If fewer than V vertices are emitted, a cycle prevented the remaining work from becoming ready. Empty and disconnected graphs are valid; isolated vertices must still appear.
An ordering need not be unique. Tests should assert every edge points forward and every vertex occurs once, unless the API deliberately fixes a tie rule. Validate IDs before indexing; bound graph size and edges for untrusted input.

Common trap

Confusing a vertex that is blocked behind a cycle with proof that only that vertex participates in the cycle.

Complexity & use

O(V+E) time and O(V) auxiliary storage. Useful for build dependencies and DAG job scheduling; a static order is not itself a concurrent executor.

Try it

Trace edges 0→1, 0→2, 1→3 and 2→3; then add 3→0.

Worked solution

The initial queue is [0]. Emitting 0 makes 1 and 2 ready. Only after both leave the queue does 3 reach indegree zero. Adding 3→0 leaves no initially ready vertex, so the processed count is below four and the cycle is reported.

Change the constraint

How would you produce a particular cycle as a diagnostic rather than only report that one exists?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-27. Use documentation for your pinned runtime, driver and tool version.