Topological Sort

Quick Revisit

• USE WHEN: ordering tasks with dependencies, DP on DAGs, detecting cycles in directed graphs
• INVARIANT: every edge (u,v) has u before v in the ordering; exists iff graph is a DAG
• TIME: O(V + E) | SPACE: O(V)
• CLASSIC BUG: forgetting to check for cycles (toposort on a cyclic graph silently gives wrong order)
• PRACTICE: ../12-practice-ladders/05-ladder-graphs.md

AL-14 | Linear ordering of vertices in a directed acyclic graph (DAG) such that for every edge $u\to v$, vertex $u$ appears before $v$ -- the backbone of dependency resolution problems on CF.

Difficulty: [Intermediate]Prerequisites: BFS, DFS and Tree DFSCF Rating: 1400-1700

Contest Frequency: [2/3] Regular -- appears in DAG and dependency problems

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Common Mistakes
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Recap
• Further Reading

---

Intuition

The Pain

You are a university advisor. Six courses have prerequisite chains:

  Courses 0-5 with prerequisites (edges = "must take before"):

      0 -----> 2 -----> 4
      |        ^        |
      |       /         v
      v     /           5
      1 --+
      |
      v
      3

  Edges: 0->1, 0->2, 1->2, 1->3, 2->4, 4->5

You need a semester-by-semester schedule that never places a course before its prerequisite. How many brute-force orderings would you check?

$6!=720$ permutations for just 6 courses. For $n$ courses the search space is $O(n!)$ -- completely unusable once $n$ exceeds ~12. We need a way to build a valid ordering directly instead of guessing.

The Key Insight

Process nodes with no remaining dependencies first -- remove them, and repeat.

Think of a cooking recipe. You cannot frost a cake before baking it, and you cannot bake it before mixing the batter. But at any moment you can do any step whose ingredients and prior steps are already done. Pick such a step, finish it, cross it off the list, and look again. As long as there are no circular dependencies (you can't have step A require B and B require A), you will eventually finish everything.

Kahn's algorithm is exactly this idea applied to a graph: maintain a count of "remaining prerequisites" (in-degree) for every node. Nodes whose count is zero are ready. Process one, remove its outgoing edges (decrement neighbors' in-degrees), and any neighbor that drops to zero becomes ready.

Visual Walkthrough

We trace Kahn's BFS on the 6-course DAG above.

Setup. Compute the in-degree of each node from the edge list:

  in-deg:  0:0   1:1   2:2   3:1   4:1   5:1
                                                queue: [0]
                                                result: []

Node 0 is the only one with in-degree 0, so it enters the queue.

Step 1 -- process node 0. Pop 0, append to result. Decrement neighbors 1 and 2.

  in-deg:  0:-   1:0   2:1   3:1   4:1   5:1
                                                queue: [1]
                                                result: [0]

Node 1 drops to 0 and enters the queue.

Step 2 -- process node 1. Pop 1, append to result. Decrement neighbors 2 and 3.

  in-deg:  0:-   1:-   2:0   3:0   4:1   5:1
                                                queue: [2, 3]
                                                result: [0, 1]

Both 2 and 3 drop to 0 -- both enqueued.

Step 3 -- process node 2. Pop 2, append to result. Decrement neighbor 4.

  in-deg:  0:-   1:-   2:-   3:0   4:0   5:1
                                                queue: [3, 4]
                                                result: [0, 1, 2]

Step 4 -- process node 3. Pop 3 (no outgoing edges).

  in-deg:  0:-   1:-   2:-   3:-   4:0   5:1
                                                queue: [4]
                                                result: [0, 1, 2, 3]

Step 5 -- process node 4. Pop 4, decrement neighbor 5.

  in-deg:  0:-   1:-   2:-   3:-   4:-   5:0
                                                queue: [5]
                                                result: [0, 1, 2, 3, 4]

Step 6 -- process node 5. Pop 5. Queue empty.

  result: [0, 1, 2, 3, 4, 5]     (6 == n --> no cycle, valid toposort)

If the result had fewer than $n$ nodes, some nodes were trapped in a cycle -- their in-degree never reached 0.

Three Questions Toposort Answers

A single Kahn's pass actually answers three related questions about a directed graph. It is worth keeping them separate when reading a problem:

Question	How Kahn's tells you
Is there some valid order?	Yes iff order.size() == n (no cycle).
Is there a cycle?	Yes iff order.size() < n. The unprocessed nodes are exactly the ones trapped in cycles.
Is the valid order unique?	Yes iff at every step the queue contains exactly one ready node. Two ready nodes means a free choice was made.

The third question is the common contest twist: "is there exactly one schedule that works?" or "does this DAG have a Hamiltonian path?" Both are equivalent to the queue never holding more than one element.

Which Variant to Reach For

Kahn's BFS is the contest default: it is iterative (no stack-overflow worry), it detects cycles by counting, and it adapts cleanly to the lex-smallest variant by swapping the queue for a min-heap. The DFS variant is shorter to write but easier to misuse — beginners often forget to reverse the post-order, or use a single visited array instead of three colors and false-flag forward/cross edges as cycles.

Reach for DFS-based toposort when you specifically want to extend it to strongly connected components (Tarjan/Kosaraju) or you want the natural post-order numbering for a tree DP. For everything else, prefer Kahn's.

The Invariant

Invariant. At every point during the algorithm:

1. Every node already in result has all of its prerequisites already in result (earlier positions).

2. The in-degree value of every remaining node equals exactly the number of its prerequisite edges whose source is also still remaining.

Property (1) guarantees the output is a valid topological ordering. Property (2) guarantees that when a remaining node's in-degree reaches zero, it truly has no unmet dependencies, so it is safe to output next.

When to Reach for This

Trigger phrases in problem statements:

• "ordering with dependencies"
• "directed acyclic graph" / "DAG"
• "course prerequisites" / "task scheduling"
• "build order" / "compilation order"
• "DP on a DAG" (toposort first, then relax)

Counter-examples -- when toposort does NOT apply:

• The graph has (or may have) cycles. Toposort is defined only on DAGs. If cycles are possible, you must either detect and reject, or first condense SCCs into a DAG.
• The graph is undirected. An undirected edge $\{u,v\}$ creates a trivial 2-cycle ($u\to v$ and $v\to u$). Toposort requires directed edges.
• You need shortest paths with negative weights -- toposort + DP handles DAGs, but for general graphs use Bellman-Ford.

What the Code Won't Teach You

Toposort is the preprocessing step -- the computation happens after.

The algorithm produces an ordering, not an answer. Almost every useful application layers a DP on top: longest path, shortest path, path count, critical path. The toposort ensures you process each node only after all its dependencies, making a single left-to-right pass sufficient.

  Step 1: Toposort                  Step 2: DP on the order
  +---+---+---+---+---+            +---+---+---+---+---+
  | 0 | 1 | 2 | 3 | 4 |  order    | 0 | 1 | 3 | 5 | 7 |  dp[]
  +---+---+---+---+---+            +---+---+---+---+---+
    ^                                 ^
    |                                 |
  "In what order should              "Given this order, what is
   I process nodes?"                  the longest/shortest/count?"

  The toposort alone doesn't answer the problem.
  It sets up the DP that answers it.

Kahn's = iterative + cycle detection built-in. DFS = recursive + SCC-extensible.

Both produce valid orderings in $O(n+m)$. The choice depends on what else you need:

  +-------------------------------+-----------------------------+
  | Need                          | Prefer                      |
  +-------------------------------+-----------------------------+
  | Cycle detection?              | Kahn's (result.size() < n)  |
  | Lex-smallest order?           | Kahn's + min-heap           |
  | SCCs later?                   | DFS (extends to Tarjan)     |
  | Iterative (no stack overflow)?| Kahn's                      |
  | Reverse-toposort?             | DFS (natural finish order)  |
  +-------------------------------+-----------------------------+

The "dependency" reduction is the hard part, not the algorithm.

Recognizing that a problem is a toposort problem is harder than implementing toposort. Any time you see "A must come before B" or "B depends on A," model it as an edge $A\to B$ and toposort. The reduction from problem statement to DAG is the creative step.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
vector<vector<int>> adj(n)	<vector>	Adjacency list representation	$O(n+m)$ space
vector<int> indeg(n, 0)	<vector>	In-degree array for Kahn's	$O(n)$
queue<int> q	<queue>	BFS queue for Kahn's algorithm	$O(1)$ push/pop
priority_queue<int, vector<int>, greater<int>> pq	<queue>	Min-heap for lex-smallest toposort	$O(\log n)$ push/pop
stack<int> st	<stack>	For DFS-based finish-order collection	$O(1)$ push/pop
vector<int> color(n, 0)	<vector>	0=white, 1=gray, 2=black for DFS cycle detection	$O(n)$

---

Implementation (Contest-Ready)

Version 1a: Kahn's BFS -- Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);

    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }

    queue<int> q;
    for(int i = 0; i < n; i++)
        if(indeg[i] == 0) q.push(i);

    vector<int> order;
    while(!q.empty()){
        int u = q.front(); q.pop();
        order.push_back(u);
        for(int v : adj[u])
            if(--indeg[v] == 0) q.push(v);
    }

    if((int)order.size() < n){
        cout << "IMPOSSIBLE\n"; // cycle exists
    } else {
        for(int i = 0; i < n; i++)
            cout << order[i] << " \n"[i == n - 1];
    }
}

Version 1b: DFS-Based -- Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> color(n, 0); // 0=white, 1=gray, 2=black
    vector<int> order;
    bool has_cycle = false;

    auto dfs = [&](auto& self, int u) -> void {
        color[u] = 1;
        for(int v : adj[u]){
            if(color[v] == 1){ has_cycle = true; return; }
            if(color[v] == 0) self(self, v);
            if(has_cycle) return;
        }
        color[u] = 2;
        order.push_back(u);
    };

    for(int i = 0; i < n; i++)
        if(color[i] == 0) dfs(dfs, i);

    if(has_cycle){
        cout << "IMPOSSIBLE\n";
    } else {
        reverse(order.begin(), order.end());
        for(int i = 0; i < n; i++)
            cout << order[i] << " \n"[i == n - 1];
    }
}

Version 2: Explained -- Kahn's BFS with Cycle Detection

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // Build adjacency list and count in-degrees.
    // indeg[v] = number of edges pointing INTO v.
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);

    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }

    // Seed the queue with all vertices that have no prerequisites
    // (in-degree 0). These can safely go first in the ordering.
    queue<int> q;
    for(int i = 0; i < n; i++)
        if(indeg[i] == 0) q.push(i);

    vector<int> order;
    order.reserve(n);

    while(!q.empty()){
        int u = q.front(); q.pop();
        order.push_back(u);

        // "Remove" u from the graph by decrementing in-degrees
        // of all its neighbors. If a neighbor's in-degree drops
        // to 0, it has no remaining prerequisites and can be queued.
        for(int v : adj[u]){
            if(--indeg[v] == 0)
                q.push(v);
        }
    }

    // If we couldn't process all n vertices, some vertices are
    // trapped in a cycle (their in-degree never reached 0).
    if((int)order.size() < n){
        cout << "IMPOSSIBLE\n";
    } else {
        for(int i = 0; i < n; i++)
            cout << order[i] << " \n"[i == n - 1];
    }
}

Version 2b: Explained -- DFS-Based with Cycle Detection

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }

    // Three-color DFS:
    //   0 (white) = unvisited
    //   1 (gray)  = currently on the recursion stack
    //   2 (black) = fully processed
    // A back edge to a gray node means a cycle.
    vector<int> color(n, 0);
    vector<int> order;
    bool has_cycle = false;

    auto dfs = [&](auto& self, int u) -> void {
        color[u] = 1; // mark as in-progress

        for(int v : adj[u]){
            if(color[v] == 1){
                // Back edge: v is an ancestor currently on the stack.
                has_cycle = true;
                return;
            }
            if(color[v] == 0)
                self(self, v);
            if(has_cycle) return; // early exit once cycle found
        }

        color[u] = 2; // fully done
        // Append u AFTER all descendants are processed.
        // Reversing this list at the end gives a valid toposort.
        order.push_back(u);
    };

    for(int i = 0; i < n; i++){
        if(color[i] == 0) dfs(dfs, i);
        if(has_cycle) break;
    }

    if(has_cycle){
        cout << "IMPOSSIBLE\n";
    } else {
        reverse(order.begin(), order.end());
        for(int i = 0; i < n; i++)
            cout << order[i] << " \n"[i == n - 1];
    }
}

---

Operations Reference

Both Kahn's and DFS run in $O(n+m)$, but the lex-smallest variant pays a logarithmic factor for the min-heap.

Operation	Time	Space
Build adjacency list + in-degrees	$O(n+m)$	$O(n+m)$
Kahn's BFS toposort	$O(n+m)$	$O(n)$ (queue + result)
DFS-based toposort	$O(n+m)$	$O(n)$ (color + stack + result)
Cycle detection (either method)	$O(n+m)$	$O(n)$
Lexicographically smallest toposort (Kahn's + min-heap)	$O((n+m)\log n)$	$O(n)$

---

Why This Works -- DFS Post-Order Reversal

Claim: Reversing the DFS post-order gives a valid topological ordering.

Proof sketch: For any edge $u\to v$, DFS finishes $v$ before $u$ (either $v$ is visited during $u$'s DFS and thus finishes first, or $v$ was already fully processed). So $v$ appears before $u$ in post-order, meaning $u$ appears before $v$ in the reversed post-order -- exactly what topological order requires.

Equivalently (Kahn's algorithm): Repeatedly remove a node with in-degree 0. This works because a DAG always has at least one such node (otherwise, follow edges backward forever -- impossible in a finite acyclic graph). Removing it and reducing in-degrees preserves the DAG property, so we can repeat.

Problem Patterns & Tricks

Pattern 1: Course Scheduling / Dependency Resolution

Given $n$ tasks with prerequisite constraints, determine a valid execution order or report it's impossible. Direct application of Kahn's or DFS toposort.

// Read prerequisites, build adj + indeg, run Kahn's.
// If result.size() < n, output "IMPOSSIBLE".

CF examples: CF 1385E, CF 510C

---

Pattern 2: Longest Path in a DAG (DP on Toposort)

Process vertices in topological order and relax edges: $dp[v]=max(dp[v],dp[u]+w(u,v))$. This is the standard way to compute longest (or shortest) paths in DAGs in $O(n+m)$.

vector<int> dp(n, 0);
for(int u : order)
    for(auto [v, w] : adj[u])
        dp[v] = max(dp[v], dp[u] + w);
// Answer: *max_element(dp.begin(), dp.end())

CF examples: CF 721C, CSES Longest Flight Route

---

Pattern 3: Lexicographically Smallest Topological Order

Replace the queue in Kahn's with a priority_queue<int, vector<int>, greater<int>> (min-heap). Always pick the smallest available vertex. Costs $O((n+m)\log n)$ instead of $O(n+m)$.

priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 0; i < n; i++)
    if(indeg[i] == 0) pq.push(i);
vector<int> order;
while(!pq.empty()){
    int u = pq.top(); pq.pop();
    order.push_back(u);
    for(int v : adj[u])
        if(--indeg[v] == 0) pq.push(v);
}

CF examples: CF 1385E, CF 1017D

---

Pattern 4: Counting the Number of Paths in a DAG

Process vertices in toposort order. For each edge $u\to v$, accumulate $paths[v]+=paths[u]$. Initialize source vertices with $paths[s]=1$.

vector<long long> paths(n, 0);
paths[source] = 1;
for(int u : order)
    for(int v : adj[u])
        paths[v] = (paths[v] + paths[u]) % MOD;

CF examples: CSES Counting Rooms, CF 1547E

---

Pattern 5: Detecting Unique Topological Order

A toposort is unique if and only if at every step of Kahn's algorithm the queue contains exactly one vertex. If at any step the queue has $\ge 2$ vertices, multiple valid orderings exist (meaning the DAG has no Hamiltonian path).

bool unique = true;
while(!q.empty()){
    if(q.size() > 1) unique = false;
    int u = q.front(); q.pop();
    // ... standard Kahn's
}

CF examples: CF 1159D

---

Pattern 6: SCC Condensation + Toposort

For general directed graphs (possibly with cycles), first find strongly connected components (Tarjan/Kosaraju), condense each SCC into a single node to form a DAG, then toposort the condensation. This pattern appears in 2-SAT and reachability problems.

CF examples: CF 427C, CF 505D

---

Pattern 7: Alien Dictionary / Order from Constraints

Given pairwise comparison information (e.g., sorted strings in an unknown alphabet), build a DAG of character ordering constraints, then toposort to recover the alphabet. Cycle = inconsistent data.

// Compare adjacent words to extract edge constraints
for(int i = 0; i + 1 < (int)words.size(); i++){
    string &a = words[i], &b = words[i+1];
    for(int j = 0; j < min(a.size(), b.size()); j++){
        if(a[j] != b[j]){
            adj[a[j] - 'a'].push_back(b[j] - 'a');
            indeg[b[j] - 'a']++;
            break;
        }
    }
}
// Then run Kahn's on the 26-letter graph

CF examples: CF 510C

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                 TOPOLOGICAL SORT CHEAT SHEET                 |
+--------------------------------------------------------------+
| WHEN TO USE:                                                 |
|   - Order tasks/nodes respecting dependencies (DAG)          |
|   - DP on a DAG (longest path, counting paths)               |
|   - Cycle detection in directed graph                        |
|   - Reconstruct ordering from pairwise constraints           |
+--------------------------------------------------------------+
| KAHN'S (BFS):                                                |
|   indeg[v]++ per edge; queue all indeg==0                    |
|   pop u, push u to result, --indeg[v] for neighbors          |
|   cycle <=> result.size() < n                                |
+--------------------------------------------------------------+
| DFS-BASED:                                                   |
|   3-color: 0=white, 1=gray, 2=black                         |
|   push to order on finish; reverse at end                    |
|   cycle <=> DFS reaches a gray node                          |
+--------------------------------------------------------------+
| LEX-SMALLEST: replace queue with min-heap  O((n+m) log n)   |
| UNIQUE ORDER: queue never has > 1 element during Kahn's     |
+--------------------------------------------------------------+
| COMPLEXITY:  O(n + m) time, O(n + m) space                   |
+--------------------------------------------------------------+

---

Common Mistakes

1. Not detecting cycles. On a cyclic graph, toposort silently produces an incomplete ordering. With Kahn's, check order.size() < n. With DFS, check for back edges (gray-node revisit). Never assume the input is acyclic unless the problem guarantees it.

2. Confusing Kahn's with DFS-based. Kahn's (BFS-based) naturally supports lexicographically smallest ordering (swap queue for min-heap) and has built-in cycle detection via result size. DFS-based is simpler when you just need any valid order and extends naturally to SCCs and DP. Pick the right variant for your problem.

3. Forgetting that toposort is only defined for DAGs. Undirected graphs have trivial 2-cycles. Graphs with cycles need SCC condensation first. If the problem involves cycles, toposort alone is the wrong tool.

---

Gotchas & Debugging

Gotcha 1: Forgetting to Check for Cycles

If the problem says "DAG," you might skip the check -- but if the input isn't guaranteed acyclic, always verify. With Kahn's: order.size() < n. With DFS: gray-node back edge.

Gotcha 2: 0-Indexed vs 1-Indexed Vertices

Many CF problems use 1-indexed vertices. If you allocate vector<vector<int>> adj(n) instead of adj(n + 1), you'll get out-of-bounds. Match your adjacency list size to the vertex numbering.

Gotcha 3: Not Starting DFS from All Vertices

If the graph is disconnected, you must loop for(int i = 0; i < n; i++) if(!visited[i]) dfs(i);. Missing this skips entire components.

Gotcha 4: Reversed Order in DFS Toposort

DFS-based toposort produces vertices in reverse finish order. You must reverse(order) at the end (or push to a stack and pop). Forgetting this gives the exact opposite of a valid order.

Gotcha 5: Duplicate Edges Inflating In-Degree

If the input can have duplicate edges $u\to v$, each duplicate increments indeg[v]. Either deduplicate edges or accept that Kahn's still works (it just decrements multiple times). But be aware for problems that count distinct dependencies.

Gotcha 6: Stack Overflow on DFS with Large $n$

Recursive DFS on $n>{10}^5$ can overflow the default stack. Use iterative DFS or increase the stack size (ulimit -s unlimited or pragma on Windows).

// Iterative DFS toposort to avoid stack overflow
vector<int> order;
vector<int> color(n, 0);
for(int start = 0; start < n; start++){
    if(color[start]) continue;
    stack<pair<int,int>> stk; // {node, edge_index}
    stk.push({start, 0});
    color[start] = 1;
    while(!stk.empty()){
        auto& [u, idx] = stk.top();
        if(idx < (int)adj[u].size()){
            int v = adj[u][idx++];
            if(color[v] == 1){ /* cycle */ }
            if(color[v] == 0){
                color[v] = 1;
                stk.push({v, 0});
            }
        } else {
            color[u] = 2;
            order.push_back(u);
            stk.pop();
        }
    }
}
reverse(order.begin(), order.end());

Gotcha 7: Confusing Toposort with Shortest Path

Toposort gives an ordering, not a shortest path. To get shortest/longest paths, you need DP on top of the toposort order.

Mental Traps

Trap 1: "DFS finish order is the topological order."

It is the reverse. DFS pushes a node to the result when it finishes (all descendants explored). The last node to finish is a source (no prerequisites) -- it should be first. You must reverse at the end:

  DAG: 0 -> 1 -> 2

  DFS from 0:
    Visit 0 -> Visit 1 -> Visit 2
    Finish 2 -> push 2      result = [2]
    Finish 1 -> push 1      result = [2, 1]
    Finish 0 -> push 0      result = [2, 1, 0]

    Finish order:  [2, 1, 0]     <-- REVERSE toposort!
    Toposort:      [0, 1, 2]     <-- after reverse()

  Forgetting reverse() gives [2, 1, 0]:
    Edge 0->1: node 0 at position 2, node 1 at position 1.
    Position(0) > Position(1) --> VIOLATION!

  +---+---+---+          +---+---+---+
  | 2 | 1 | 0 |  WRONG   | 0 | 1 | 2 |  CORRECT
  +---+---+---+          +---+---+---+
    ^                       ^
    Finish order            After reverse

Trap 2: "If Kahn's queue has multiple elements, the answer is wrong."

Multiple elements in the queue means multiple valid topological orders exist -- not that the algorithm is broken. The output is still a valid toposort. The queue size tells you about uniqueness, not correctness:

  DAG:  0 -> 2       Kahn's queue trace:
        1 -> 2
                      Step 1: indeg = {0:0, 1:0, 2:2}
                              Queue = [0, 1]  <-- TWO elements!
                              Both orderings are valid:
                                [0, 1, 2]  and  [1, 0, 2]

  +-------+-------------------+--------------------+
  | Queue | Interpretation    | Action             |
  | size  |                   |                    |
  +-------+-------------------+--------------------+
  |   0   | Cycle! (if not    | Report impossible  |
  |       | all nodes done)   |                    |
  +-------+-------------------+--------------------+
  |   1   | Forced choice     | Unique ordering    |
  +-------+-------------------+--------------------+
  |  >= 2 | Multiple valid    | Any is correct;    |
  |       | orderings exist   | pick min for lex   |
  +-------+-------------------+--------------------+

---

Self-Test

Answer without looking at the code above.

• [ ] Kahn's from memory. Write Kahn's algorithm: in-degree computation, queue initialization, main loop, and the cycle detection check.
• [ ] DFS reversal. Why does DFS-based toposort require reversing the result? What happens if you skip the reverse?
• [ ] Cycle detection. How does Kahn's detect a cycle? How does DFS detect a cycle? State both conditions.
• [ ] Lex-smallest order. What data structure replaces the queue to produce the lexicographically smallest topological order? What is the new time complexity?
• [ ] DP on toposort. Given a DAG with weighted edges, write the DP recurrence for the longest path using topological order.

Bug Gallery

Bug 1: Kahn's algorithm -- forgetting isolated vertices (no edges)

vector<int> indeg(n + 1, 0);
for (int u = 1; u <= n; u++)
    for (int v : adj[u])
        indeg[v]++;

queue<int> q;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0 && !adj[i].empty()) q.push(i);  // BUG

Why it's wrong: Vertices with no incoming and no outgoing edges are still valid DAG nodes with in-degree 0. The !adj[i].empty() filter excludes them, producing incomplete topological orders.

Fix:

if (indeg[i] == 0) q.push(i);  // OK: all zero-indegree nodes, including isolated ones

---

Bug 2: DFS toposort -- using vis but no in_stack for cycle detection

vector<bool> vis(n + 1, false);
bool has_cycle = false;

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (vis[v]) { has_cycle = true; return; }  // BUG
        if (!vis[v]) dfs(v);
    }
    order.push_back(u);
}

Why it's wrong: A visited node isn't necessarily on the current DFS path -- it may have been fully processed in an earlier DFS call. This false-flags cross edges and forward edges as cycles. You need a separate in_stack[] (or a 3-color scheme) to track nodes on the current recursion path.

Fix:

vector<int> color(n + 1, 0);  // 0=white, 1=gray, 2=black
void dfs(int u) {
    color[u] = 1;  // gray = on current path
    for (int v : adj[u]) {
        if (color[v] == 1) { has_cycle = true; return; }  // OK: back edge
        if (color[v] == 0) dfs(v);
    }
    color[u] = 2;  // black = fully processed
    order.push_back(u);
}

---

Bug 3: Kahn's with multiple components -- using wrong vertex range

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);  // 0-indexed
vector<int> indeg(n, 0);
for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;  // 1-indexed input!
    adj[u].push_back(v);      // BUG: 1-indexed into 0-indexed array
    indeg[v]++;
}

Why it's wrong: If the input is 1-indexed (vertices 1..n) but the arrays are sized for 0-indexed (0..n-1), vertex n writes out of bounds. This is one of the most common contest bugs with graph algorithms.

Fix:

vector<vector<int>> adj(n + 1);  // OK: size for 1-indexed
vector<int> indeg(n + 1, 0);
// Or convert: adj[u-1].push_back(v-1); indeg[v-1]++;

---

Bug 4: No cycle detection -- assuming the input is always a DAG

vector<int> toposort(int n) {
    queue<int> q;
    vector<int> order;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return order;  // BUG: no check for cycle
}

Why it's wrong: If the graph has a cycle, some nodes never reach in-degree 0 and are silently omitted. The returned order has fewer than n nodes but the caller doesn't know. This leads to downstream bugs in DP or scheduling that are extremely hard to trace.

Fix:

if ((int)order.size() != n) {
    // OK: cycle detected -- not all nodes were processed
    return {};  // or throw / set a flag
}
return order;

---

Bug 5: Forgetting to reverse the result in DFS-based toposort

vector<int> order;
vector<bool> vis(n + 1, false);

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v);
    order.push_back(u);
}
// Call dfs for all nodes, then use order directly  <-- BUG

Why it's wrong: DFS toposort appends a node after all its descendants are processed. This produces reverse topological order. Without reversing, dependencies appear after the nodes that depend on them, breaking any algorithm that processes nodes in topological order.

Fix:

// After all DFS calls complete:
reverse(order.begin(), order.end());  // OK: reverse to get correct order

---

Bug 6: Wrong in-degree -- adding reverse edges for a directed graph

int n, m;
cin >> n >> m;
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);  // BUG: undirected edge in a DAG
    indeg[v]++;
}

Why it's wrong: Adding the reverse edge adj[v].push_back(u) treats the graph as undirected, but topological sort only applies to directed acyclic graphs. The reverse edges create artificial cycles and corrupt in-degree counts, causing Kahn's to produce wrong results or miss nodes entirely.

Fix:

adj[u].push_back(v);  // OK: directed edge only
indeg[v]++;
// Do NOT add adj[v].push_back(u) for toposort

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Course Schedule	CSES	Easy (1400)	Direct Kahn's toposort, print order or report impossible
2	Fox and Names	CF 510C	Easy (1400)	Build letter-order DAG from sorted strings, toposort
3	Directing Edges	CF 1385E	Medium (1500)	Orient undirected edges to keep DAG, then toposort
4	Longest Flight Route	CSES	Medium (1600)	Longest path in DAG via DP on toposort order
5	Game Routes	CSES	Medium (1600)	Count paths in DAG using toposort + DP
6	Journey	CF 721C	Medium (1600)	Longest path in DAG with edge weights
7	Substring Order I	CF 1547E	Medium (1600)	Toposort + reachability
8	Parallel Courses	CF 1159D	Medium-Hard (1800)	Check uniqueness of toposort (queue size at each step)
9	Checkposts	CF 427C	Medium-Hard (1800)	SCC condensation + DAG processing
10	Mr. Kitayuta's Gift	CF 505D	Hard (2000)	SCC + toposort on condensed graph

---

Rating Progression

CF Rating	What You Should Be Comfortable With
1200	Detect if toposort exists (cycle detection), basic Kahn's algorithm
1500	Lex-smallest toposort, DFS-based toposort, using toposort order for DP
1800	Uniqueness check, SCC condensation -> DAG -> toposort, multi-criteria ordering
2100	Online toposort with incremental edges, toposort on implicit DAGs (state-space), counting valid topological orders

The Mistake That Teaches

The bug: You implement DFS-based toposort, but the output order is wrong:

vector<int> order;
void dfs(int u) {
    visited[u] = true;
    order.push_back(u);  // BUG: adding on entry
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}
// then use `order` as topological order

The lesson: DFS-based toposort adds nodes in post-order (after visiting all descendants), then reverses the result. Adding on entry gives you DFS pre-order, which is NOT a valid topological order. Fix: move order.push_back(u) to after the for-loop, then reverse order at the end.

Debug This

Bug 1: Kahn's algorithm processes only some nodes:

vector<int> indeg(n + 1, 0);
for (int u = 1; u <= n; u++)
    for (int v : adj[u])
        indeg[v]++;

queue<int> q;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) q.push(i);

vector<int> order;
while (!q.empty()) {
    int u = q.front(); q.pop();
    order.push_back(u);
    for (int v : adj[u]) {
        indeg[v]--;
        if (indeg[v] == 0) q.push(v);
    }
}
// order.size() < n ... why?

Answer

If order.size() < n, the graph has a cycle. Nodes in the cycle never reach in-degree 0, so they're never enqueued. This is actually the correct behavior of Kahn's algorithm -- it doubles as a cycle detector. The "bug" is expecting all nodes to appear when the graph isn't a DAG.

Bug 2: DFS toposort gives wrong order on this DAG:

vector<int> result;
vector<bool> vis(n + 1, false);
void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v);
    result.push_back(u);
}
for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs(i);
// uses result directly without reversing

Answer

DFS-based toposort produces nodes in reverse topological order (post-order). You must reverse the result vector before using it. Fix: add reverse(result.begin(), result.end()); after the loop.

Bug 3: Lex-smallest toposort is wrong:

priority_queue<int> pq;  // max-heap!
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) pq.push(i);
while (!pq.empty()) {
    int u = pq.top(); pq.pop();
    order.push_back(u);
    for (int v : adj[u]) {
        if (--indeg[v] == 0) pq.push(v);
    }
}

Answer

priority_queue<int> in C++ is a max-heap by default. This gives the lexicographically largest order. For lex-smallest, use priority_queue<int, vector<int>, greater<int>> (min-heap).

Historical Origin

Topological sorting was first described by Edward Kahn in 1962 as a method for scheduling tasks with precedence constraints, originally applied to project management (PERT charts). The DFS-based approach was later formalized by Tarjan as part of his foundational DFS framework.

Mnemonic Anchor

"No incoming edges? You're free to go first." Kahn's algorithm in one sentence: repeatedly remove nodes with zero in-degree. That's the topological order.

---

Recap

Topological sort isn't "sorting" in the comparison sense -- it linearizes a partial order. A DAG says which things must come before which; toposort picks one valid total order.

Key takeaways:

• Two algorithms, same complexity. Kahn's (BFS, iterative, cycle detection via result size) and DFS-based (recursive, post-order reversal, extends to SCCs). Both run in $O(V+E)$.
• Toposort is preprocessing. The real computation is usually a DP layered on top of the ordering (longest path, shortest path, path count).
• The hard part is the reduction. Recognizing "A must come before B" as a DAG edge is the creative step; the algorithm itself is mechanical.
• Cycle detection is mandatory unless the problem guarantees a DAG.
• Counting distinct topological orderings is #P-complete for general DAGs -- no polynomial algorithm exists.

---

Further Reading

• cp-algorithms: Topological Sorting -- both Kahn's and DFS approaches with proofs.
• CF Blog: Topological Sort and its Applications -- community discussion and problem links.
• cppreference: std::queue -- BFS queue reference.
• cppreference: std::priority_queue -- for lex-smallest toposort variant.
• See: 03-dfs-and-tree-dfs.md for the DFS foundation underlying DFS-based toposort.
• See: 04-scc-and-2sat.md for SCC condensation into a DAG before toposorting.
• See: 02-dp-intro-1d.md for DP techniques commonly applied on toposort orderings.

Related Techniques

• DFS and Tree DFS -- DFS-based toposort uses reverse post-order of a depth-first search
• BFS -- Kahn's algorithm is a BFS-style layer-by-layer processing of zero-indegree nodes
• DP on DAG -- topological order is the natural iteration order for DP on directed acyclic graphs
• SCC and 2-SAT -- condense SCCs first, then toposort the resulting DAG
• Graph modeling guide -- recognizing when a problem reduces to a DAG
• Practice problems -- graph problem ladder including toposort