rust / LEVEL 4

The dependency graph that never starts

EST.45 MIN

THEORY / RETRIEVAL

What to restore

Apply Kahn's algorithm using indegrees
Deduplicate repeated edges before counting
Use a min-priority frontier for deterministic output

Zero indegree is the executable frontier

Kahn's algorithm starts with nodes that have no remaining prerequisites. Removing one node decrements its outgoing neighbors; newly-zero neighbors join the frontier. If fewer than N nodes are emitted, a cycle prevents a topological order.

Determinism needs an explicit tie-break

Many valid orders can exist. Tests, build systems and distributed workflows benefit from a stable contract, so this task always chooses the smallest available node. Duplicate input edges must not inflate indegree twice.

CHECKPOINT

After Kahn's algorithm empties its frontier, only 7 of 9 nodes were emitted. What does that prove?

Confidence: 3/5

02 / IMPLEMENTATION

Implement the contract

Return the lexicographically smallest topological order for nodes 0..node_count. Edges are prerequisite→dependent. Ignore duplicate edges, reject endpoints outside the node range, and return Cycle when not every node can be emitted.

Initializing editor…

CLOUD SANDBOXnetwork off · 256 MB · 12 s

1 / 64 KB

OUTPUT

Runner is waiting for a submission.