What signals in a problem statement indicate the Build the graph, then sort sub-pattern?

"sorted lexicographically by the rules of a new language"; "is nums the only shortest supersequence"; "print all possible orders"

Build the graph, then sort (Topological Sort Sub-pattern)

Q: What makes Build the graph, then sort different from other sub-patterns?

**Alien Dictionary** (GFG and LeetCode) adds one edge per adjacent word pair and must catch the prefix case. **Sequence Reconstruction** builds edges from consecutive pairs and checks the order is **unique** (queue size 1 at every step). **All Tasks Scheduling Orders** backtracks over every free node and restores in-degrees after each choice.

The dependencies are hidden in the input (sorted words, sequences, pairs) and must be turned into edges first.

Signals in the problem statement

›
"sorted lexicographically by the rules of a new language"
›
"is nums the only shortest supersequence"
›
"print all possible orders"

What makes it different

Alien Dictionary (GFG and LeetCode) adds one edge per adjacent word pair and must catch the prefix case. Sequence Reconstruction builds edges from consecutive pairs and checks the order is unique (queue size 1 at every step). All Tasks Scheduling Orders backtracks over every free node and restores in-degrees after each choice.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Alien Dictionary
Basic Anchor·GeeksforGeeks
WalkthroughHard
2
Alien Dictionary
Basic Reinforcement·LeetCode #269 Premium
WalkthroughHard
3
Sequence Reconstruction
Slight Variation·LeetCode #444 Premium
WalkthroughMedium
4
All Tasks Scheduling Orders
Medium·Educative
WalkthroughHard

Template

build-graph-template.cpp

// Alien dictionary: each adjacent pair of words gives at most one edge, from their first difference.
string alienOrder(const vector<string>& words) {
    vector<vector<bool>> edge(26, vector<bool>(26, false));
    vector<int> indeg(26, 0);
    vector<bool> used(26, false);
    for (auto& w : words) for (char ch : w) used[ch - 'a'] = true;
    for (int i = 0; i + 1 < (int)words.size(); i++) {
        const string &a = words[i], &b = words[i + 1];
        int j = 0;
        while (j < (int)min(a.size(), b.size()) && a[j] == b[j]) j++;
        if (j == (int)min(a.size(), b.size())) {
            if (a.size() > b.size()) return "";   // "abc" before "ab": no order works
            continue;                             // a prefix tells us nothing
        }
        int u = a[j] - 'a', v = b[j] - 'a';       // only the FIRST difference matters
        if (!edge[u][v]) { edge[u][v] = true; indeg[v]++; }
    }
    queue<int> q;                                 // then plain Kahn over the used letters
    for (int c = 0; c < 26; c++) if (used[c] && indeg[c] == 0) q.push(c);
    string order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order += char('a' + u);
        for (int v = 0; v < 26; v++)
            if (edge[u][v] && --indeg[v] == 0) q.push(v);
    }
    return order.size() == (size_t)count(used.begin(), used.end(), true) ? order : "";
}

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

DFS order / DAG DP