Step 4 of 6

Topological sort

Build systems, package managers, spreadsheets and job schedulers must run tasks after their dependencies. For a directed graph with no cycles, a topological order lists every vertex before everything that depends on it.

Kahn's algorithm:

1. Count each vertex's in-degree (how many edges point to it).
2. Put every vertex with in-degree 0 in a queue: nothing blocks it.
3. Pop one, append it to the order, and decrement the in-degree of its dependents; any that reach 0 join the queue.

If the order ends up shorter than n, some vertices were never freed: the graph has a cycle (for example, two libraries that depend on each other).

Your turn: write std::vector<int> build_order(int n, const std::vector<std::pair<int, int>>& deps) where {a, b} means "a must be built before b". Use a min-heap instead of a plain queue so ties come out smallest-number first (the tests expect that exact order). Return an empty vector if there's a cycle.

Previous: Depth-first flood fill Next: Dijkstra's shortest paths