Topological Sort: Doing Things in Order

Tasks that depend on other tasks

Socks before shoes; Learn C++ before DSA. Draw an arrow from each task to the tasks that need it. A topological order lists tasks so every arrow points forward.

• Count each task's in-degree: how many prerequisites it still needs.
• Tasks with in-degree 0 are ready – put them in a queue.
• Take a ready task, output it, and tick off one prerequisite for each task that depends on it. New zeros become ready.

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> name = {"underwear", "socks", "trousers", "shoes", "belt"};
    vector<pair<int, int>> rules = {{0, 2}, {1, 3}, {2, 3}, {2, 4}};   // a before b
    int n = name.size();
    vector<vector<int>> after(n);
    vector<int> indeg(n, 0);
    for (auto [a, b] : rules) {
        after[a].push_back(b);
        indeg[b]++;
    }
    queue<int> ready;
    for (int v = 0; v < n; v++)
        if (indeg[v] == 0) ready.push(v);
    int done = 0;
    while (!ready.empty()) {
        int v = ready.front();
        ready.pop();
        cout << name[v] << ' ';
        done++;
        for (int w : after[v])
            if (--indeg[w] == 0) ready.push(w);
    }
    cout << endl << (done == n ? "all tasks ordered" : "impossible: there is a cycle") << endl;
    return 0;
}

Output

underwear socks trousers shoes belt 
all tasks ordered

If A needs B and B needs A, neither ever becomes ready, so fewer than n tasks come out – that's how a cycle is detected.