SyntaxPilot
Courses/DSA and Coding Problems/Lesson 51
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 51 of 90

Topological sort: course schedule (Kahn's algorithm)

queued

These are the notes for DSA episode 51. Some subjects need others first: in what order can you take them all, or is it impossible? When a directed graph has no cycle, we can list its vertices so that every arrow points forward. That list is a topological order. We start from a real-life problem (planning engineering subjects), define every word, try the obvious brute force (rescan for a ready course, again and again) that hits Time Limit Exceeded on a 1 lakh-course chain, find the key insight (count each course's pending prerequisites, its in-degree; 0 means ready, and taking a course only changes the courses that need it), and finish with Kahn's algorithm in O(V + E), which also detects cycles. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

You've just joined engineering, and you must plan all your subjects. Some subjects need others first: Data Structures needs Programming; Algorithms needs Data Structures and Maths. You need an order where every subject comes after everything it needs. And if the rules say A needs B and B needs A, no order exists: the plan is impossible.

In college In the graph
A subject a vertex (a course)
"Take Programming before Data Structures" an arrow Programming → Data Structures
The number of pending prerequisites of a subject its in-degree
Subjects you may take right now vertices with in-degree 0, waiting in a queue
Passing a subject removing its arrows: each dependent's in-degree drops by 1
A semester plan where everything fits a topological order
"A needs B and B needs A" a cycle: no order exists

Every word, from zero

  • Prerequisite: a course you must finish before another. Dependency: the other way round: Data Structures depends on Programming.
  • Directed edge (arrow) b → a: "take b before a". We draw it from the prerequisite to the course that needs it.
  • DAG (directed acyclic graph): a directed graph with no cycle. Only DAGs have a topological order.
  • Topological order (topological sort): a list of all vertices where every arrow goes from an earlier vertex to a later one. A DAG can have many valid orders.
  • In-degree: the number of arrows coming into a vertex. Here: how many prerequisites are still pending.
  • Out-degree: the number of arrows going out.
  • Queue: first in, first out (ArrayDeque: add, poll).
  • Kahn's algorithm: repeatedly take a vertex with in-degree 0, append it to the order, and remove its outgoing arrows. Published by A. B. Kahn in 1962.
  • Level (of Kahn's algorithm): all the courses that become ready at the same time; one semester in practice 1.

Problem statement

LeetCode 207, Course Schedule: there are numCourses courses 0..n-1. prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses.

LeetCode 210, Course Schedule II: same input; return one valid order, or an empty array if it is impossible.

n prerequisites 210 answer 207 answer
2 [1,0] [0, 1] true
2 [1,0], [0,1] [] false
4 [1,0], [2,0], [3,1], [3,2] [0, 1, 2, 3] (also [0, 2, 1, 3]) true

Careful: in [a, b] the prerequisite is the second number. LeetCode allows up to 2,000 courses; we also test 1 lakh.

Brute force: look for a ready course, again and again

The way you'd do it on paper: scan the courses for one not taken yet whose prerequisites are all done (check every pair), take it, write it down, repeat n times. If no course is ready but some are left, they're waiting for each other: return [].

import java.util.*;

public class Main {
    static int[] findOrder(int n, int[][] pre) {
        boolean[] done = new boolean[n];
        int[] order = new int[n];
        for (int k = 0; k < n; k++) {
            int pick = -1;
            for (int c = 0; c < n && pick == -1; c++) {
                if (done[c]) continue;
                boolean ready = true;
                for (int[] p : pre)
                    if (p[0] == c && !done[p[1]]) { ready = false; break; }
                if (ready) pick = c;
            }
            if (pick == -1) return new int[0];
            done[pick] = true; order[k] = pick;
        }
        return order;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}})));
        System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
        System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}})));
    }
}
[0, 1]
[0, 1, 2, 3]
[]

A 1 lakh-course chain: Time Limit Exceeded

Course 0 needs 1, 1 needs 2, and so on, so course 99999 must come first.

        int n = 100000;
        int[][] pre = new int[n - 1][];
        for (int i = 0; i + 1 < n; i++) pre[i] = new int[]{i, i + 1};
        long t0 = System.nanoTime();
        int[] order = findOrder(n, pre);
        System.out.println(order.length + " courses, first " + order[0] + ", "
            + (System.nanoTime() - t0) / 1000000 + " ms");
(no output: Time Limit Exceeded after 8 seconds)

Why it is slow

n picks × a scan of up to n courses × a check of all E pairs: O(n × n × E). And it's wasteful: after every pick we ask every course again, "are you ready now?", although finishing one course can only change the answer for the courses that need it.

The key insight: count the pending prerequisites

On a checklist In code
"Pending prerequisites: 2" written on each subject indeg[c]: arrows coming in
Pending 0: you may take it now courses with indeg == 0 go into a queue
Pass a subject, tell only the ones that need it for each arrow c → d: indeg[d]--
A subject's number hits 0 it joins the queue

Walkthrough on example 3 (0 → 1, 0 → 2, 1 → 3, 2 → 3):

in-degree: 0:0  1:1  2:1  3:2      queue [0]
take 0  →  1:0  2:0  3:2           queue [1, 2]     order 0
take 1  →  3:1                     queue [2]        order 0 1
take 2  →  3:0                     queue [3]        order 0 1 2
take 3                             queue []         order 0 1 2 3   (4 of 4: possible)

And a cycle? 2 → 0, 0 → 1, 1 → 2: every course has in-degree 1, nobody is ever ready, the queue is empty from the start, and we take 0 of 3 courses. Taking fewer than n courses means there is a cycle. So Kahn's algorithm also detects cycles, with no recursion at all.

Steps:

  1. For every pair [a, b]: arrow b → a, indeg[a]++.
  2. Every course with indeg == 0 goes into the queue.
  3. Poll c, append it to the order.
  4. For each arrow c → d: indeg[d]--; if it becomes 0, add d.
  5. Took all n? Return the order; otherwise return [] (a cycle).

The optimal solution in Java: Kahn's algorithm

import java.util.*;

public class Main {
    static int[] findOrder(int n, int[][] pre) {
        List<List<Integer>> next = new ArrayList<>();
        for (int c = 0; c < n; c++) next.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
        int[] order = new int[n];
        int k = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            order[k++] = c;
            for (int d : next.get(c))
                if (--indeg[d] == 0) q.add(d);
        }
        return k == n ? order : new int[0];
    }
    static boolean canFinish(int n, int[][] pre) {
        return findOrder(n, pre).length == n;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}})));
        System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
        System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}})));
        System.out.println(Arrays.toString(findOrder(3, new int[][]{})));
        System.out.println(Arrays.toString(findOrder(3, new int[][]{{0, 1}, {1, 2}, {2, 0}})));
        System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }
}
[0, 1]
[0, 1, 2, 3]
[]
[0, 1, 2]
[]
false

The three examples; then 3 courses with no prerequisites ([0, 1, 2]), a 3-course cycle ([]), and canFinish on the impossible pair (false).

The 1 lakh chain:

100000 courses, first 99999, 60 ms

The same solution in C++

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

vector<int> findOrder(int n, const vector<pair<int, int>>& pre) {   // pair {a, b}: take b before a
    vector<vector<int>> next(n);
    vector<int> indeg(n, 0);
    for (auto [a, b] : pre) { next[b].push_back(a); indeg[a]++; }
    queue<int> q;
    for (int c = 0; c < n; c++) if (indeg[c] == 0) q.push(c);
    vector<int> order;
    while (!q.empty()) {
        int c = q.front(); q.pop();
        order.push_back(c);
        for (int d : next[c])
            if (--indeg[d] == 0) q.push(d);
    }
    if ((int)order.size() < n) return {};      // a cycle: impossible
    return order;
}

bool canFinish(int n, const vector<pair<int, int>>& pre) { return (int)findOrder(n, pre).size() == n; }

void show(const vector<int>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
    cout << "]\n";
}

int main() {
    show(findOrder(2, {{1, 0}}));                              // [0, 1]
    show(findOrder(4, {{1, 0}, {2, 0}, {3, 1}, {3, 2}}));      // [0, 1, 2, 3]
    show(findOrder(2, {{1, 0}, {0, 1}}));                      // []
    cout << boolalpha << canFinish(2, {{1, 0}, {0, 1}}) << "\n";   // false
}
[0, 1]
[0, 1, 2, 3]
[]
false

The same solution in Python

from collections import deque

def find_order(n, pre):               # [a, b]: take b before a
    nxt = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in pre:
        nxt[b].append(a)
        indeg[a] += 1
    q = deque(c for c in range(n) if indeg[c] == 0)
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for d in nxt[c]:
            indeg[d] -= 1
            if indeg[d] == 0:
                q.append(d)
    return order if len(order) == n else []

def can_finish(n, pre):
    return len(find_order(n, pre)) == n

print(find_order(2, [[1, 0]]))                            # [0, 1]
print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))    # [0, 1, 2, 3]
print(find_order(2, [[1, 0], [0, 1]]))                    # []
print(can_finish(2, [[1, 0], [0, 1]]))                    # False
[0, 1]
[0, 1, 2, 3]
[]
False

The other way: DFS (episode 50)

A three-colour DFS also gives a topological order: when a vertex turns black, append it to a list; the reverse of that list is a topological order (a vertex is finished only after everything it points to). An arrow to a grey vertex means a cycle. Kahn's algorithm is usually preferred in interviews: no recursion, and the cycle check is a simple count.

Three real bugs

Bug 1: drawing the arrow backwards

import java.util.*;

public class Main {
    static int[] findOrder(int n, int[][] pre) {
        List<List<Integer>> next = new ArrayList<>();
        for (int c = 0; c < n; c++) next.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : pre) { next.get(p[0]).add(p[1]); indeg[p[1]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
        int[] order = new int[n];
        int k = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            order[k++] = c;
            for (int d : next.get(c))
                if (--indeg[d] == 0) q.add(d);
        }
        return k == n ? order : new int[0];
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
    }
}
[3, 1, 2, 0]

[3, 1, 2, 0]: every course before its prerequisites. In a pair [a, b], b comes first: the arrow goes from b to a.

Bug 2: no check that all n courses were taken

import java.util.*;

public class Main {
    static int[] findOrder(int n, int[][] pre) {
        List<List<Integer>> next = new ArrayList<>();
        for (int c = 0; c < n; c++) next.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
        int[] order = new int[n];
        int k = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            order[k++] = c;
            for (int d : next.get(c))
                if (--indeg[d] == 0) q.add(d);
        }
        return order;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(3, new int[][]{{1, 0}, {2, 1}, {1, 2}})));
    }
}
[0, 0, 0]

[0, 0, 0]. Courses 1 and 2 need each other, so only course 0 was taken; the rest of the array is Java's default zeros. It looks like an answer but it's garbage. Always compare k with n.

Bug 3: adding a course every time its count drops

import java.util.*;

public class Main {
    static int[] findOrder(int n, int[][] pre) {
        List<List<Integer>> next = new ArrayList<>();
        for (int c = 0; c < n; c++) next.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
        int[] order = new int[n];
        int k = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            order[k++] = c;
            for (int d : next.get(c))
                { indeg[d]--; q.add(d); }
        }
        return k == n ? order : new int[0];
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
    }
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
    at Main.findOrder(Main.java:15)
    at Main.main(Main.java:22)

Course 3 went into the queue twice (once for each prerequisite), so we tried to write a fifth course into an array of four. And the first time, course 2 wasn't done yet. A course is ready only when its count is exactly 0.

Complexity

Approach Time Space 1 lakh chain
Rescan for a ready course O(n × n × E) O(n) Time Limit Exceeded
Kahn's algorithm O(V + E) O(V + E) milliseconds
DFS, reverse finishing order O(V + E) O(V + E) (use an iterative DFS for deep chains)

Kahn's algorithm puts each course in the queue once and crosses out each arrow once.

Common mistakes

Mistake What you see (real) Why Fix
Arrow a → b for pair [a, b] [3, 1, 2, 0] every rule broken arrow b → a, indeg[a]++
No k == n check [0, 0, 0] a cycle stops the queue early k == n ? order : new int[0]
Add d whenever indeg drops ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4 d queued twice, too early add only when it reaches 0
Rescanning for a ready course Time Limit Exceeded O(n × n × E) in-degree + queue
Expecting one exact order "wrong answer" on your own tests many orders are valid check that every arrow points forward

Mini project: the semester planner

Subjects with prerequisites in, subjects per semester out. Kahn's algorithm level by level (freeze q.size(), exactly like the minutes of rotting oranges) gives the minimum number of semesters when any number of subjects fit in one semester.

import java.util.*;

public class Main {
    // Mini project: a semester planner. Subjects with prerequisites -> subjects per semester (Kahn level by level).
    public static void main(String[] args) {
        String[] subj = {"Programming", "Maths", "Data Structures", "Databases", "Algorithms", "Operating Systems", "Compilers"};
        String[][] needs = {{"Data Structures", "Programming"}, {"Databases", "Programming"}, {"Algorithms", "Data Structures"},
                            {"Algorithms", "Maths"}, {"Operating Systems", "Data Structures"}, {"Compilers", "Algorithms"},
                            {"Compilers", "Operating Systems"}};
        Map<String, Integer> id = new HashMap<>();
        for (int i = 0; i < subj.length; i++) id.put(subj[i], i);
        int n = subj.length;
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < n; i++) next.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (String[] p : needs) { next.get(id.get(p[1])).add(id.get(p[0])); indeg[id.get(p[0])]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
        int sem = 0, taken = 0;
        while (!q.isEmpty()) {
            sem++;
            List<String> now = new ArrayList<>();
            for (int size = q.size(); size > 0; size--) {
                int c = q.poll(); now.add(subj[c]); taken++;
                for (int d : next.get(c)) if (--indeg[d] == 0) q.add(d);
            }
            System.out.println("Semester " + sem + ": " + String.join(", ", now));
        }
        System.out.println(taken == n ? "All " + n + " subjects planned" : "Impossible: a cycle of prerequisites");
    }
}
Semester 1: Programming, Maths
Semester 2: Data Structures, Databases
Semester 3: Algorithms, Operating Systems
Semester 4: Compilers
All 7 subjects planned

Practice

1. Parallel Courses (LeetCode 1136). Courses 1..n, relations[i] = [prev, next]. In one semester you may take any number of courses whose prerequisites are done. Minimum number of semesters, or -1.

Solution
import java.util.*;

public class Main {
    // Parallel Courses (LeetCode 1136): courses 1..n, relation {prev, next}; any number of courses per semester.
    // Minimum semesters = the number of Kahn LEVELS (like the minutes in rotting oranges). -1 if there is a cycle.
    static int minimumSemesters(int n, int[][] relations) {
        List<List<Integer>> next = new ArrayList<>();
        for (int c = 0; c <= n; c++) next.add(new ArrayList<>());
        int[] indeg = new int[n + 1];
        for (int[] r : relations) { next.get(r[0]).add(r[1]); indeg[r[1]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int c = 1; c <= n; c++) if (indeg[c] == 0) q.add(c);
        int semesters = 0, taken = 0;
        while (!q.isEmpty()) {
            semesters++;
            for (int size = q.size(); size > 0; size--) {
                int c = q.poll(); taken++;
                for (int d : next.get(c)) if (--indeg[d] == 0) q.add(d);
            }
        }
        return taken == n ? semesters : -1;
    }
    public static void main(String[] args) {
        System.out.println(minimumSemesters(3, new int[][]{{1, 3}, {2, 3}}));
        System.out.println(minimumSemesters(3, new int[][]{{1, 2}, {2, 3}, {3, 1}}));
    }
}
2
-1

2. Alien Dictionary. Words are sorted in an unknown alphabet. Find one valid order of the letters (empty if impossible).

Solution

Compare neighbouring words: the first position where they differ gives an arrow (the first word's letter comes before the second's). Then Kahn's algorithm on the letters. A word followed by its own prefix ("abc" before "ab") is impossible.

import java.util.*;

public class Main {
    // Alien Dictionary: words sorted in an unknown alphabet; find one valid letter order ("" if impossible).
    // Two neighbouring words: the first letter where they differ gives an arrow  a -> b.
    static String alienOrder(String[] words) {
        Map<Character, Set<Character>> next = new TreeMap<>();
        Map<Character, Integer> indeg = new TreeMap<>();
        for (String w : words) for (char ch : w.toCharArray()) { next.putIfAbsent(ch, new TreeSet<>()); indeg.putIfAbsent(ch, 0); }
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            if (a.length() > b.length() && a.startsWith(b)) return "";       // "abc" before "ab": impossible
            for (int k = 0; k < Math.min(a.length(), b.length()); k++)
                if (a.charAt(k) != b.charAt(k)) {
                    if (next.get(a.charAt(k)).add(b.charAt(k))) indeg.merge(b.charAt(k), 1, Integer::sum);
                    break;
                }
        }
        Deque<Character> q = new ArrayDeque<>();
        for (var e : indeg.entrySet()) if (e.getValue() == 0) q.add(e.getKey());
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char c = q.poll(); sb.append(c);
            for (char d : next.get(c)) if (indeg.merge(d, -1, Integer::sum) == 0) q.add(d);
        }
        return sb.length() == indeg.size() ? sb.toString() : "";
    }
    public static void main(String[] args) {
        System.out.println(alienOrder(new String[]{"wrt", "wrf", "er", "ett", "rftt"}));
        System.out.println("[" + alienOrder(new String[]{"z", "x", "z"}) + "]");
    }
}
wertf
[]

3. The smallest-numbered valid order. Among all valid orders, return the one that is smallest when read left to right.

Solution

Use a min-heap (PriorityQueue, episode 43) instead of the queue, so the smallest ready course is always taken first. Time O((V + E) log V).

import java.util.*;

public class Main {
    // The smallest-numbered valid order: replace the queue with a min-heap, so the smallest ready course is taken first.
    static int[] smallestOrder(int n, int[][] pre) {
        List<List<Integer>> next = new ArrayList<>();
        for (int c = 0; c < n; c++) next.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int c = 0; c < n; c++) if (indeg[c] == 0) pq.add(c);
        int[] order = new int[n]; int k = 0;
        while (!pq.isEmpty()) {
            int c = pq.poll(); order[k++] = c;
            for (int d : next.get(c)) if (--indeg[d] == 0) pq.add(d);
        }
        return k == n ? order : new int[0];
    }
    public static void main(String[] args) {
        // 3 needs 4, 1 needs 4, 2 needs 0
        System.out.println(Arrays.toString(smallestOrder(5, new int[][]{{3, 4}, {1, 4}, {2, 0}})));
    }
}
[0, 2, 4, 1, 3]

4. Is a given order valid? Given n, the prerequisites and a proposed order, check it.

Solution

Store pos[course] = index in the order (and check every course appears exactly once). Then for every pair [a, b], the order is valid only if pos[b] < pos[a]. O(V + E).

Quick quiz

n = 4, pairs [1,0] [2,1] [3,0] (take b before a). Which order is not valid?

A) 0, 3, 1, 2 B) 0, 1, 3, 2 C) 0, 1, 2, 3 D) 3, 0, 1, 2

Answer

D. Course 3 needs course 0, so 3 can't come before 0. The other three keep 0 before 1 and 3, and 1 before 2: there can be many topological orders.

Interview questions

  1. What is a topological order, and when does one exist? An order of all vertices where every arrow points forward. It exists exactly when the directed graph has no cycle (a DAG).
  2. How does Kahn's algorithm detect a cycle? Vertices on a cycle never reach in-degree 0, so fewer than n vertices are output.
  3. Why a queue? Would a stack work? Any container works: every vertex taken has in-degree 0, so any order of taking them is valid. A queue gives levels (useful for "minimum semesters"); a min-heap gives the smallest order.
  4. Kahn vs DFS? Both O(V + E). Kahn: iterative, simple cycle check, natural levels. DFS: reverse of finishing order; needs an iterative version for deep graphs.
  5. What does [a, b] mean in LeetCode 207? Take b before a: the arrow is b → a. Getting this backwards is the most common bug.
  6. Real uses? Build systems (compile a file after the files it imports), package managers, spreadsheet recalculation, task scheduling, course planning.

Glossary

Term Meaning
Prerequisite A course that must come first
Dependency "A depends on B": A needs B first
Arrow b → a Take b before a
DAG Directed acyclic graph: directed, no cycle
Topological order Every arrow points from earlier to later
In-degree / out-degree Arrows coming in / going out
Kahn's algorithm Take in-degree-0 vertices, remove their arrows, repeat
Level Vertices that become ready together
Cycle A path back to its start; makes an order impossible
Min-heap Always gives the smallest element first (PriorityQueue)
O(V + E) Time that grows with vertices plus edges

Summary

  • Prerequisites are arrows from the first course to the later one; in LeetCode's [a, b], b comes first.
  • A topological order makes every arrow point forward; there can be many.
  • Kahn's algorithm: count in-degrees, queue the zeros, poll, cross out arrows, queue new zeros.
  • Fewer than n taken = a cycle = impossible.
  • O(V + E) time and space.
  • Next episode: Dijkstra's algorithm, shortest paths when every edge has a weight.