2. Which node can I place first?

One that no edge points into: **in-degree 0**. For edges `0→2, 1→2, 1→3`: in-degrees are 0, 0, 2, 1. Nodes 0 and 1 can go first. Place 0: node 2 drops to 1. Place 1: node 2 drops to 0 and node 3 drops to 0, so both are free now.

3. How does a cycle show up?

In a cycle `2 → 4 → 5 → 2`, each of the three nodes keeps in-degree ≥ 1 forever, because the edge into it comes from another node of the cycle that is never placed. Kahn's queue empties early: **placed < V means a cycle**. No extra code is needed.

4. Why can't I just use a visited set with DFS for directed cycles?

Because reaching a visited node again isn't always a loop. In `0→1→3` and `0→2→3`, node 3 is reached twice but there's no cycle. You need **three colours**: grey = on the current path, black = finished. Only an edge into a **grey** node closes a cycle.

5. How do I compute something that flows along the edges?

Process nodes in topological order, so a node's inputs are always ready. With Kahn: when you pop u, push its value to each successor (`finish[v] = max(finish[v], finish[u] + time[v])`). With DFS: **memoise** `f(u) = combine(f(v) for v after u)`; each node is solved once, O(V + E).

6. Where does the graph come from when none is given?

From comparisons. In a sorted alien dictionary, `"wrt"` before `"wrf"` says only that **t comes before f**: the first letter that differs. Letters after it say nothing. Compare only **adjacent** words, add one edge per pair, then run Kahn on the letters.

7. What if the order must be unique, or I need all of them?

The order is unique exactly when the queue **never holds more than one node**: two free nodes could go in either order. To list all orders, try each free node in turn, recurse, then **undo** (restore the in-degrees): backtracking on top of Kahn.

Topological Sort Pattern — Intuition, Sub-patterns & C++ Templates

Q: 1. Which way do the edges point?

Decide it once and write it down: **edge u → v means u comes first**. Course Schedule gives `[a, b]` meaning "to take a you must first take b", so the edge is **b → a**. Getting this backwards gives the order reversed, which fails for every edge.

Q: 4. Why can't I just use a visited set with DFS for directed cycles?

Because reaching a visited node again isn't always a loop. In `0→1→3` and `0→2→3`, node 3 is reached twice but there's no cycle. You need **three colours**: grey = on the current path, black = finished. Only an edge into a **grey** node closes a cycle.

Q: 5. How do I compute something that flows along the edges?

Process nodes in topological order, so a node's inputs are always ready. With Kahn: when you pop u, push its value to each successor (`finish[v] = max(finish[v], finish[u] + time[v])`). With DFS: **memoise** `f(u) = combine(f(v) for v after u)`; each node is solved once, O(V + E).

Q: 6. Where does the graph come from when none is given?

From comparisons. In a sorted alien dictionary, `"wrt"` before `"wrf"` says only that **t comes before f**: the first letter that differs. Letters after it say nothing. Compare only **adjacent** words, add one edge per pair, then run Kahn on the letters.

Q: 7. What if the order must be unique, or I need all of them?

The order is unique exactly when the queue **never holds more than one node**: two free nodes could go in either order. To list all orders, try each free node in turn, recurse, then **undo** (restore the in-degrees): backtracking on top of Kahn.

Q: What is the difference between Kahn (BFS on in-degrees) and DFS finishing order?

Both give a valid order in O(V + E). Kahn detects a cycle by counting and naturally gives **levels** (semesters). DFS fits when you also compute a value per node (memo). Pick Kahn when unsure: no recursion depth limits.

Q: What is the difference between Directed cycle (three colours) and Undirected cycle (visited + parent)?

In a directed graph, a visited node reached again may just be a second road to it (`0→1→3`, `0→2→3`). Only a node still **on the current path** closes a cycle. In an undirected graph any visited node other than the parent closes one.

Q: What is the difference between Edge `[a, b]` = a → b and Edge `[a, b]` = b → a?

Read the statement: "to take a you must first take b" makes b the prerequisite, so the arrow is **b → a**. A reversed graph gives the order backwards and no error message.

A

What is this pattern?

A topological order lists the nodes of a directed graph so that every edge points forward: if u → v means "u must come before v", then u appears earlier in the list. Course plans, build steps and task schedules are all this question.

The idea behind Kahn's algorithm: a node with in-degree 0 (no arrow points into it) has no prerequisites left, so it is safe to place now. Place it, delete its outgoing edges, and some other nodes may drop to in-degree 0. Repeat with a queue. Each node and edge is handled once: O(V + E).

An order exists only if there is no cycle: in a cycle every node waits for another one, so none of them ever reaches in-degree 0. That makes the same algorithm a cycle detector: if fewer than V nodes get placed, there is a cycle. The DFS view gives the same results: finishing order reversed is a topological order, and an edge back to a node still on the DFS path is a cycle. Memoised DFS over a DAG also computes DP along the dependencies (longest path, earliest finish time).

Getting dressed. Socks before shoes, underwear before trousers, trousers before shoes, shirt before tie. At any moment you can put on any item that has nothing left that must go on first (in-degree 0). Putting on socks frees the shoes from one of their two requirements; once the trousers are on too, the shoes are free. If the rules ever said "shoes before socks" as well, you'd stand there forever: that's a cycle.

B

See it move

Blue = in the queue (in-degree 0), purple = popped now, green = placed. in = unplaced prerequisites.

Kahn's algorithm: place what has no prerequisites leftn = 6, edges = [[0,2],[1,2],[1,3],[2,4],[3,4],[4,5],[3,5]]step 1/8

prerequisites (u → v: u first)

queue

0

1

0

1

▲front

order

Start: in-degree 0 → 0, 1

in = how many unplaced prerequisites a node still has. Nodes 0 and 1 have none, so they can go first: both start in the queue. Blue = in the queue, purple = popped now, green = placed.

Blue = grey (on the current path), green = black (finished), red = the edge that closes a cycle, orange = an edge to a finished node (safe).

Cycle check: three-colour DFSn = 6, edges = [[0,1],[0,2],[1,3],[2,3],[2,4],[4,5],[5,2]]step 1/12

directed graph

path

All nodes white

white = not visited, grey = on the current DFS path (blue), black = finished, every path from it checked (green). A cycle shows up as an edge into a grey node.

C

How do I recognise it?

"Prerequisites", "depends on", "must be done before", "build order", "course schedule".
"Can all tasks be finished?" → is the dependency graph free of cycles?
"Return any valid order" / "return all valid orders" of tasks.
"Minimum number of semesters / time to finish" when tasks run in parallel → Kahn level by level, or the longest path in the DAG.
Sorted words in an unknown alphabet → the letter order is hidden in the first difference of adjacent words.
"Safe" / "eventually terminal" nodes, or anything that must not lead into a loop.

Looks like Topological Sort, but isn't

Undirected graph: "is there a cycle?", "connected?"

→ Union-Find or Graph BFS / DFS

In-degree and "before" only make sense when edges have a direction. An undirected cycle check uses Union-Find (an edge inside one group) or DFS with a parent check.

Shortest path from a start node

→ Graph BFS or Dijkstra

Topological sort gives an order of all nodes, not distances from one start. (On a DAG you can compute shortest/longest paths in topological order, but that's the DAG DP use, not plain sorting.)

Order intervals or tasks by start time / deadline

→ Intervals or Greedy

Sorting by a number needs no graph. Topological sort is for pairwise rules ("a before b") that don't come from a single key.

D

How would I discover it from scratch?

Don't memorise “use topological sort”. Ask these questions in order — the pattern falls out.

Decide it once and write it down: edge u → v means u comes first. Course Schedule gives [a, b] meaning "to take a you must first take b", so the edge is b → a. Getting this backwards gives the order reversed, which fails for every edge.

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Kahn's algorithm (BFS)

5 questions

Produce an order (or a schedule) where every prerequisite comes first.

02

Cycle detection / feasibility

3 questions

Decide whether an order exists at all, or which nodes can never reach a cycle.

03

DFS order / DAG DP

3 questions

Compute a value for every node that depends on the nodes after it (or before it) in a DAG.

04

Build the graph, then sort

4 questions

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

F

Don't mix these up

Kahn (BFS on in-degrees) vs DFS finishing order

Both give a valid order in O(V + E). Kahn detects a cycle by counting and naturally gives levels (semesters). DFS fits when you also compute a value per node (memo). Pick Kahn when unsure: no recursion depth limits.

Directed cycle (three colours) vs Undirected cycle (visited + parent)

In a directed graph, a visited node reached again may just be a second road to it (0→1→3, 0→2→3). Only a node still on the current path closes a cycle. In an undirected graph any visited node other than the parent closes one.

Edge `[a, b]` = a → b vs Edge `[a, b]` = b → a

Read the statement: "to take a you must first take b" makes b the prerequisite, so the arrow is b → a. A reversed graph gives the order backwards and no error message.

Any valid order vs The only valid order

Kahn with a queue that ever holds two nodes has a free choice there, so more than one order exists. Uniqueness = the queue size is exactly 1 at every step.

G

Code templates (C++)

Kahn's algorithm (BFS on in-degrees)

Count in-degrees, queue every 0, pop → append → lower successors. Returns {} when fewer than n nodes are placed (a cycle). Parallel Courses counts the levels of this loop instead of the order.

kahn-template.cpp

// Kahn's algorithm: repeatedly take a node nothing points to any more.
vector<int> topoSort(int n, const vector<vector<int>>& edges) {   // edge {u, v} = u must come before v
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); indeg[e[1]]++; }
    queue<int> q;
    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);                       // everything before u is already placed
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);       // v's last prerequisite just got placed
    }
    if ((int)order.size() < n) return {};         // some nodes never reached in-degree 0: a cycle
    return order;
}

Cycle check: three-colour DFS

Grey = on the current path, black = finished. An edge into grey is a back edge, a cycle; an edge into black is just another road to a node already checked.

cycle-dfs-template.cpp

// Directed cycle check with three colours: 0 = not seen, 1 = on the current path, 2 = finished.
bool dfsCycle(int u, const vector<vector<int>>& adj, vector<int>& color) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 1) return true;           // back edge to the current path: a cycle
        if (color[v] == 0 && dfsCycle(v, adj, color)) return true;
    }
    color[u] = 2;                                 // every path from u is cycle-free
    return false;
}

bool hasCycle(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) adj[e[0]].push_back(e[1]);
    vector<int> color(n, 0);
    for (int u = 0; u < n; u++)
        if (color[u] == 0 && dfsCycle(u, adj, color)) return true;
    return false;
}

DAG DP with a memoised DFS

A node's answer is built from its successors' answers, each solved once. Longest Increasing Path, Loud and Rich and Parallel Courses III all have this shape; the memo also acts as the visited set.

dag-dp-template.cpp

// DP on a DAG with a memoised DFS: a node's answer is built from its successors' answers.
// Here: the longest path (in nodes) that starts at each node.
int longestFrom(int u, const vector<vector<int>>& adj, vector<int>& memo) {
    if (memo[u] != 0) return memo[u];             // already solved: each node is solved once
    int best = 1;
    for (int v : adj[u]) best = max(best, 1 + longestFrom(v, adj, memo));
    return memo[u] = best;
}

int longestPath(int n, const vector<vector<int>>& edges) {   // the graph must be a DAG
    vector<vector<int>> adj(n);
    for (auto& e : edges) adj[e[0]].push_back(e[1]);
    vector<int> memo(n, 0);
    int ans = 0;
    for (int u = 0; u < n; u++) ans = max(ans, longestFrom(u, adj, memo));
    return ans;
}

Build the graph from comparisons (Alien Dictionary)

One edge per adjacent pair of words, from their first difference. A longer word before its own prefix is impossible. Then Kahn over the letters that appear.

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 : "";
}

Topological Sort Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide