Step 4 of 6

Topological sort

Build systems, package managers, spreadsheets and job schedulers must run tasks after their dependencies: compile before linking, install a library before the app that uses it. Model each task as a vertex and each "a must come before b" as a directed edge a → b. 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: how many things it's waiting for).
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 everything that depends on it. Any that reach 0 are now unblocked and join the queue.

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<std::string> step = {"shop", "cook", "set table", "eat", "wash up"};
    std::vector<std::pair<int, int>> before = {{0, 1}, {1, 3}, {2, 3}, {3, 4}};

    std::vector<std::vector<int>> next(step.size());
    std::vector<int> indegree(step.size(), 0);
    for (auto [a, b] : before) {
        next[a].push_back(b);
        indegree[b]++;
    }

    std::queue<int> ready;
    for (int v = 0; v < (int)step.size(); v++) if (indegree[v] == 0) ready.push(v);

    std::vector<int> order;
    while (!ready.empty()) {
        int v = ready.front();
        ready.pop();
        order.push_back(v);
        for (int w : next[v]) {
            if (--indegree[w] == 0) ready.push(w);    // its last blocker is done
        }
    }
    for (int v : order) std::cout << step[v] << " -> ";
    std::cout << (order.size() == step.size() ? "done" : "cycle!") << "\n";
}

shop -> set table -> cook -> eat -> wash up -> done

Reading the result

shop and set table have nothing before them, so both start in the queue. eat waits until both cook and set table are done (its in-degree drops from 2 to 0), and wash up comes last. Several valid orders usually exist; this one depends on the order vertices join the queue.

Detecting cycles

If a vertex is part of a cycle (a depends on b, b depends on a), its in-degree never reaches 0, so it never joins the queue. So if the final order is shorter than n, the graph has a cycle, and there's no valid order.

Your task: deterministic ties

Your version must produce one exact order: when several vertices are ready at once, take the smallest number first. Replace the queue with a min-heap, std::priority_queue<int, std::vector<int>, std::greater<int>>, and use top() instead of front().

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