Kahn's Algorithm

You Already Know This Algorithm -- You Just Don't Know It

Every time you figure out what to do first by asking "what has no prerequisites?", you're running Kahn's algorithm in your head. Pick something with no blockers, do it, cross it off, repeat. That's the entire algorithm.

The difference between you and a computer is that you eyeball it. Kahn's algorithm tracks blockers with a single integer per node: the in-degree.

---

What Is Topological Sort?

A topological ordering of a directed graph is a linear sequence of all vertices such that for every edge u -> v, u appears before v in the sequence.

Two immediate consequences:

1. Only DAGs have topological orderings. If there's a cycle A -> B -> C -> A, then A must come before B, B before C, and C before A. Impossible.
2. A DAG can have many valid topological orderings. Unless the constraints fully determine the order, multiple answers exist.

💡 Key insight. Topological sort answers: "In what order can I process these tasks so that every dependency is satisfied before the task that needs it?"

---

The In-Degree Idea

The in-degree of a node is the number of edges pointing into it. A node with in-degree 0 has no prerequisites. It's safe to process first.

After you process a node, it's "done." Every edge leaving it no longer matters. Removing those edges may drop other nodes to in-degree 0, making them newly available.

That's the entire loop.

---

Kahn's Algorithm

vector<int> kahn(int n) {
    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]) {
            if (--indeg[v] == 0)
                q.push(v);
        }
    }
    return order;
}

Three steps:

1. Seed: Push all in-degree-0 nodes into a queue.
2. Process: Pop a node, add it to the result, decrement in-degree of each neighbor.
3. Propagate: If any neighbor's in-degree drops to 0, push it.

When the queue empties, you're done.

---

Full Trace

Consider this 6-node DAG:

1 → 2 → 5
1 → 3 → 5
3 → 4 → 6
2 → 4

Adjacency list: 1:[2,3], 2:[4,5], 3:[4,5], 4:[6], 5:[], 6:[]

Initial in-degrees: 1:0, 2:1, 3:1, 4:2, 5:2, 6:1

Step	Queue	Pop	Decrement in-deg	New 0-deg	Order So Far
0	{1}	--	--	1	[]
1	{}	1	2→0, 3→0	2, 3	[1]
2	{3}	2	4→1, 5→1	--	[1, 2]
3	{}	3	4→0, 5→0	4, 5	[1, 2, 3]
4	{5}	4	6→0	6	[1, 2, 3, 4]
5	{6}	5	--	--	[1, 2, 3, 4, 5]
6	{}	6	--	--	[1, 2, 3, 4, 5, 6]

Result: 1 2 3 4 5 6. All 6 nodes appear, so no cycle.

⚠ Gotcha. The trace above assumed a FIFO queue, so among nodes 2 and 3 (both available at step 1), 2 was popped first because it was pushed first. Different queue orderings give different valid topological orderings. All are correct.

---

Cycle Detection

If the graph has a cycle, some nodes will never reach in-degree 0. They block each other forever. The queue drains before all nodes are processed.

Detection rule: If order.size() < n, the graph has a cycle.

if ((int)order.size() < n) {
    cout << "IMPOSSIBLE" << endl;
}

Consider adding edge 5 -> 1 to the previous graph. Now 1's in-degree is 1. No node starts at in-degree 0 except... none. The queue starts empty, the result is empty, and we correctly report a cycle.

For a subtler case, imagine only part of the graph has a cycle. Nodes outside the cycle get processed normally; only the cyclic portion gets stuck.

💡 Key insight. Kahn's algorithm is a BFS that peels off layers of "ready" nodes. If a cycle exists, the cycle nodes form a core that can never be peeled.

---

CSES Course Schedule Walkthrough

Problem: N courses, M requirements. Each requirement says "course A must be completed before course B." Print a valid order, or "IMPOSSIBLE."

This is a direct application of Kahn's algorithm. Courses are nodes, requirements are directed edges.

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> adj[n + 1];
    vector<int> indeg(n + 1, 0);

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

    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])
            if (--indeg[v] == 0) q.push(v);
    }

    if ((int)order.size() < n) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        for (int x : order) cout << x << " ";
        cout << endl;
    }
}

Nothing fancy. The problem IS the algorithm.

---

Complexity

• Time: O(V + E). Each node enters the queue exactly once. Each edge is examined exactly once (when its source node is popped).
• Space: O(V) for the in-degree array and the queue. The adjacency list takes O(V + E) regardless.

---

When to Use Kahn's Over DFS Topo Sort

Kahn's has two practical advantages:

1. Iterative. No recursion, no stack overflow risk on large graphs.
2. Natural cycle detection. The order.size() < n check falls out for free.

DFS-based topo sort has its own strengths (covered next lesson). In contests, either works. Pick whichever you can code faster.

---

Try It

The starter code has the structure ready. Fill in the TODO sections.

Test case 1 -- DAG:

Input:
6 6
1 2
1 3
2 5
3 5
3 4
4 6

Output:
1 2 3 4 5 6
(or any valid topological order)

Test case 2 -- graph with cycle:

Input:
3 3
1 2
2 3
3 1

Output:
IMPOSSIBLE

Challenge: Modify the code to not just detect a cycle, but also print which nodes are involved in the cycle. Hint: after Kahn's terminates, any node with remaining in-degree > 0 is part of or downstream of a cycle.

---

Problems

Problem	Link	Difficulty
CSES Course Schedule	cses.fi/problemset/task/1679	Easy
LC 207 — Course Schedule	leetcode.com/problems/course-schedule	Medium
LC 210 — Course Schedule II	leetcode.com/problems/course-schedule-ii	Medium