34.03Intermediate / Advanced5 topics18 min5 interactive animations

Topological order applications

Dependency problems all reduce to topological sorting: course schedules, build systems, task pipelines, alien alphabets and package installs, each with its own way of turning the input into arrows.

Learning goals

Model a dependency problem as a graph and choose the direction of the arrows
Return a valid order, or report that none exists
Derive ordering constraints from sorted words
Compute the earliest finish time when independent tasks run in parallel

Prerequisites

Topological sortHash maps

Most real uses of topological sort begin with a different input: a list of prerequisites, a map of build targets, a sorted word list. The skill is turning that input into the right graph, and then reading the answer back.

34.03.1

Course schedule

Each course is a vertex. A prerequisite pair [a, b] (take b before a) becomes the arrow b → a. All courses can be finished exactly when the graph has no cycle, and a topological order is a valid schedule. The arrow direction is a common slip: reversing every arrow still gives a valid order of the *reverse* problem, so check with a tiny example.

The last preset in the animation, *Course schedule: 0 needs 1, 1 needs 2*, enters the arrows 2-1 and 1-0 and the order comes out 2 → 1 → 0.

Java

1static int[] findOrder(int numCourses, int[][] prerequisites) {   // pair {a, b}: b before a; empty array when impossible
2    List<List<Integer>> g = new ArrayList<>();
3    int[] indeg = new int[numCourses];
4    for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
5    for (int[] p : prerequisites) { g.get(p[1]).add(p[0]); indeg[p[0]]++; }   // arrow: prerequisite -> course
6    Deque<Integer> queue = new ArrayDeque<>();
7    for (int c = 0; c < numCourses; c++) if (indeg[c] == 0) queue.add(c);
8    int[] order = new int[numCourses];
9    int k = 0;
10    while (!queue.isEmpty()) {
11        int c = queue.poll();
12        order[k++] = c;
13        for (int next : g.get(c)) if (--indeg[next] == 0) queue.add(next);
14    }
15    return k == numCourses ? order : new int[0];
16}

Topological sort: Kahn's algorithm and reversed DFS finish order

Interactive · edit the input

directed graph · 6 vertices · 6 edges

in=2

in=1

in=0

Being processedIn-degree 0 (ready)Placed in the orderFinishedOn a cycle (never ready)

queue (front first)

in-degree

order

none yet

Setup

Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].

Step 1 / 14

Java

1List<Integer> kahn(List<List<Integer>> g) {      // topological order; shorter than n on a cycle
2    int n = g.size(); int[] indeg = new int[n];
3    for (List<Integer> out : g) for (int v : out) indeg[v]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // sources are ready
6    List<Integer> order = new ArrayList<>();
7    while (!q.isEmpty()) {
8        int u = q.poll(); order.add(u);
9        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // remove u's arrows
10    }
11    return order;                                // order.size() < n: a cycle remains
12}
13List<Integer> dfsOrder(List<List<Integer>> g) {  // reversed DFS finish order; null on a cycle
14    int n = g.size(); int[] colour = new int[n];
15    Deque<Integer> post = new ArrayDeque<>();
16    for (int s = 0; s < n; s++) if (colour[s] == 0 && !visit(g, s, colour, post)) return null;
17    return new ArrayList<>(post);
18}
19boolean visit(List<List<Integer>> g, int u, int[] colour, Deque<Integer> post) {
20    colour[u] = 1;
21    for (int v : g.get(u)) {
22        if (colour[v] == 1) return false;        // an arrow back into the stack: a cycle
23        if (colour[v] == 0 && !visit(g, v, colour, post)) return false;
24    }
25    colour[u] = 2; post.addFirst(u);             // finished after everything it points to
26    return true;
27}

Live state

0 vertices placed0 arrows removed

sources

[4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	sources=[4, 5]	Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].
2	L8	u=4 order=[4]	Take 4 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
3	L9	u=4 v=0 indeg[v]=1	4 → 0: in-degree of 0 drops to 1.
4	L9	u=4 v=1 indeg[v]=1	4 → 1: in-degree of 1 drops to 1.
5	L8	u=5 order=[4, 5]	Take 5 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
6	L9	u=5 v=2 indeg[v]=0	5 → 2: in-degree of 2 drops to 0, so 2 is ready and joins the queue.
7	L9	u=5 v=0 indeg[v]=0	5 → 0: in-degree of 0 drops to 0, so 0 is ready and joins the queue.
8	L8	u=2 order=[4, 5, 2]	Take 2 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
9	L9	u=2 v=3 indeg[v]=0	2 → 3: in-degree of 3 drops to 0, so 3 is ready and joins the queue.
10	L8	u=0 order=[4, 5, 2, 0]	Take 0 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
11	L8	u=3 order=[4, 5, 2, 0, 3]	Take 3 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
12	L9	u=3 v=1 indeg[v]=0	3 → 1: in-degree of 1 drops to 0, so 1 is ready and joins the queue.
13	L8	u=1 order=[4, 5, 2, 0, 3, 1]	Take 1 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
14	L11	return=[4, 5, 2, 0, 3, 1]	Topological order: 4 → 5 → 2 → 0 → 3 → 1. All 6 vertices were placed, which also proves the graph is acyclic. Every arrow goes from an earlier vertex to a later one.

34.03.2

Build dependencies

A build system has targets that depend on other targets: app needs lib and util; lib needs util. Draw an arrow from each dependency to the target that needs it; a topological order is a valid build sequence, and a cycle is a build error that the tool must report instead of looping.

Targets have names rather than numbers, so a map from name to dependencies replaces the arrays. Using a sorted map and sorted dependency lists makes the output deterministic, which matters for reproducible builds.

Java

1static List<String> buildOrder(Map<String, List<String>> dependsOn) {   // target -> the targets it needs; null on a cycle
2    Map<String, Integer> missing = new TreeMap<>();                      // how many dependencies are not built yet
3    Map<String, List<String>> needs = new TreeMap<>();                   // dependency -> the targets waiting for it
4    for (var e : dependsOn.entrySet()) {
5        missing.putIfAbsent(e.getKey(), 0);
6        for (String d : e.getValue()) { missing.putIfAbsent(d, 0); }
7    }
8    for (var e : dependsOn.entrySet())
9        for (String d : new TreeSet<>(e.getValue())) {
10            needs.computeIfAbsent(d, k -> new ArrayList<>()).add(e.getKey());
11            missing.merge(e.getKey(), 1, Integer::sum);
12        }
13    PriorityQueue<String> ready = new PriorityQueue<>();
14    for (var e : missing.entrySet()) if (e.getValue() == 0) ready.add(e.getKey());
15    List<String> order = new ArrayList<>();
16    while (!ready.isEmpty()) {
17        String t = ready.poll();
18        order.add(t);
19        for (String waiting : needs.getOrDefault(t, List.of()))
20            if (missing.merge(waiting, -1, Integer::sum) == 0) ready.add(waiting);
21    }
22    return order.size() == missing.size() ? order : null;
23}

Topological sort: Kahn's algorithm and reversed DFS finish order

Interactive · edit the input

directed graph · 6 vertices · 6 edges

in=2

in=1

in=0

Being processedIn-degree 0 (ready)Placed in the orderFinishedOn a cycle (never ready)

queue (front first)

in-degree

order

none yet

Setup

Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].

Step 1 / 14

Java

1List<Integer> kahn(List<List<Integer>> g) {      // topological order; shorter than n on a cycle
2    int n = g.size(); int[] indeg = new int[n];
3    for (List<Integer> out : g) for (int v : out) indeg[v]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // sources are ready
6    List<Integer> order = new ArrayList<>();
7    while (!q.isEmpty()) {
8        int u = q.poll(); order.add(u);
9        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // remove u's arrows
10    }
11    return order;                                // order.size() < n: a cycle remains
12}
13List<Integer> dfsOrder(List<List<Integer>> g) {  // reversed DFS finish order; null on a cycle
14    int n = g.size(); int[] colour = new int[n];
15    Deque<Integer> post = new ArrayDeque<>();
16    for (int s = 0; s < n; s++) if (colour[s] == 0 && !visit(g, s, colour, post)) return null;
17    return new ArrayList<>(post);
18}
19boolean visit(List<List<Integer>> g, int u, int[] colour, Deque<Integer> post) {
20    colour[u] = 1;
21    for (int v : g.get(u)) {
22        if (colour[v] == 1) return false;        // an arrow back into the stack: a cycle
23        if (colour[v] == 0 && !visit(g, v, colour, post)) return false;
24    }
25    colour[u] = 2; post.addFirst(u);             // finished after everything it points to
26    return true;
27}

Live state

0 vertices placed0 arrows removed

sources

[4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	sources=[4, 5]	Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].
2	L8	u=4 order=[4]	Take 4 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
3	L9	u=4 v=0 indeg[v]=1	4 → 0: in-degree of 0 drops to 1.
4	L9	u=4 v=1 indeg[v]=1	4 → 1: in-degree of 1 drops to 1.
5	L8	u=5 order=[4, 5]	Take 5 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
6	L9	u=5 v=2 indeg[v]=0	5 → 2: in-degree of 2 drops to 0, so 2 is ready and joins the queue.
7	L9	u=5 v=0 indeg[v]=0	5 → 0: in-degree of 0 drops to 0, so 0 is ready and joins the queue.
8	L8	u=2 order=[4, 5, 2]	Take 2 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
9	L9	u=2 v=3 indeg[v]=0	2 → 3: in-degree of 3 drops to 0, so 3 is ready and joins the queue.
10	L8	u=0 order=[4, 5, 2, 0]	Take 0 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
11	L8	u=3 order=[4, 5, 2, 0, 3]	Take 3 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
12	L9	u=3 v=1 indeg[v]=0	3 → 1: in-degree of 1 drops to 0, so 1 is ready and joins the queue.
13	L8	u=1 order=[4, 5, 2, 0, 3, 1]	Take 1 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
14	L11	return=[4, 5, 2, 0, 3, 1]	Topological order: 4 → 5 → 2 → 0 → 3 → 1. All 6 vertices were placed, which also proves the graph is acyclic. Every arrow goes from an earlier vertex to a later one.

34.03.3

Task prerequisites

When each task has a duration and independent tasks run in parallel, the question changes to *how soon can everything finish?* The earliest finish of a task is its duration plus the latest earliest-finish among its prerequisites. Process the tasks in topological order so every prerequisite is computed first; the answer is the largest finish time.

This is the critical-path method used in project planning: the longest chain of dependent tasks decides the total time, however many workers you have. The same recurrence over a DAG is the *Longest path* option of the next lesson's animation.

Java

1static int earliestFinish(int[] duration, int[][] before) {   // before[i] = {a, b}: a must finish before b starts; -1 on a cycle
2    int n = duration.length;
3    List<List<Integer>> g = new ArrayList<>();
4    int[] indeg = new int[n], finish = new int[n];
5    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
6    for (int[] e : before) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
7    Deque<Integer> queue = new ArrayDeque<>();
8    for (int i = 0; i < n; i++) if (indeg[i] == 0) { queue.add(i); finish[i] = duration[i]; }
9    int done = 0, total = 0;
10    while (!queue.isEmpty()) {
11        int u = queue.poll();
12        done++;
13        total = Math.max(total, finish[u]);
14        for (int v : g.get(u)) {
15            finish[v] = Math.max(finish[v], finish[u] + duration[v]);   // v starts after its slowest prerequisite
16            if (--indeg[v] == 0) queue.add(v);
17        }
18    }
19    return done == n ? total : -1;
20}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

directed graph · 6 vertices · 9 edges

d=0

Vertex being processedSourceReachable (value shown)Done

topological order

best[v]

-1

-2

-3

-4

-5

Setup

A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.

Step 1 / 11

Java

1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	order=[0, 1, 2, 3, 5, 4] source=0	A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2	L9	u=0 v=1 cand=5 best[v]=5	0 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3	L9	u=0 v=2 cand=3 best[v]=3	0 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4	L9	u=1 v=3 cand=11 best[v]=11	1 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5	L9	u=1 v=2 cand=7 best[v]=7	1 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6	L9	u=2 v=4 cand=11 best[v]=11	2 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7	L9	u=2 v=5 cand=9 best[v]=9	2 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8	L9	u=2 v=3 cand=14 best[v]=14	2 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9	L9	u=3 v=5 cand=15 best[v]=15	3 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10	L9	u=3 v=4 cand=15 best[v]=15	3 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11	L11	return=[0, 5, 7, 14, 15, 15] arrows relaxed=9	Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).

34.03.4

Alien dictionary

Given words sorted in an unknown alphabet, compare each neighbouring pair: the first position where they differ shows that one letter comes before another. That is one arrow. If no position differs and the first word is longer, the list is invalid, since a word cannot precede its own prefix. A topological order of the letters is a valid alphabet; a cycle means the list contradicts itself.

Only neighbouring pairs matter, because sortedness is transitive. Letters that are never compared can appear anywhere that respects the arrows, so many answers can be valid. The animation lists the rules it finds, then runs Kahn's algorithm taking the smallest letter first.

Java

1static String alienOrder(String[] words) {                      // "" when the list cannot be sorted by any alphabet
2    Map<Character, Set<Character>> out = new TreeMap<>();
3    Map<Character, Integer> indeg = new TreeMap<>();
4    for (String w : words) for (char c : w.toCharArray()) { out.putIfAbsent(c, new TreeSet<>()); indeg.putIfAbsent(c, 0); }
5    for (int i = 0; i + 1 < words.length; i++) {
6        String a = words[i], b = words[i + 1];
7        int k = 0, m = Math.min(a.length(), b.length());
8        while (k < m && a.charAt(k) == b.charAt(k)) k++;
9        if (k == m) { if (a.length() > b.length()) return ""; continue; }       // a longer word before its own prefix
10        if (out.get(a.charAt(k)).add(b.charAt(k))) indeg.merge(b.charAt(k), 1, Integer::sum);   // the first difference decides
11    }
12    PriorityQueue<Character> ready = new PriorityQueue<>();
13    for (var e : indeg.entrySet()) if (e.getValue() == 0) ready.add(e.getKey());
14    StringBuilder order = new StringBuilder();
15    while (!ready.isEmpty()) {
16        char c = ready.poll();
17        order.append(c);
18        for (char d : out.get(c)) if (indeg.merge(d, -1, Integer::sum) == 0) ready.add(d);
19    }
20    return order.length() == indeg.size() ? order.toString() : "";
21}

Alien dictionary: letter order from sorted words

Interactive · edit the input

letters: an arrow x → y means x comes before y · 4 vertices · 0 edges

Being processedReady (no letter must precede it)Placed in the orderStuck on a cycle

words

abc

abd

Setup

4 words use the letters a b c d. Two neighbouring words reveal at most one rule: the first position where they differ.

Step 1 / 10

Java

1String alienOrder(String[] words) {              // "" when no order exists
2    Map<Character, Set<Character>> out = new TreeMap<>();
3    Map<Character, Integer> indeg = new TreeMap<>();
4    for (String w : words) for (char c : w.toCharArray()) { out.putIfAbsent(c, new TreeSet<>()); indeg.putIfAbsent(c, 0); }
5    for (int i = 0; i + 1 < words.length; i++) {
6        String a = words[i], b = words[i + 1];
7        int k = 0, m = Math.min(a.length(), b.length());
8        while (k < m && a.charAt(k) == b.charAt(k)) k++;
9        if (k == m) { if (a.length() > b.length()) return ""; continue; }   // a longer word before its own prefix
10        if (out.get(a.charAt(k)).add(b.charAt(k))) indeg.merge(b.charAt(k), 1, Integer::sum);   // first difference decides
11    }
12    PriorityQueue<Character> ready = new PriorityQueue<>();
13    for (var e : indeg.entrySet()) if (e.getValue() == 0) ready.add(e.getKey());
14    StringBuilder order = new StringBuilder();
15    while (!ready.isEmpty()) {
16        char c = ready.poll(); order.append(c);
17        for (char d : out.get(c)) if (indeg.merge(d, -1, Integer::sum) == 0) ready.add(d);
18    }
19    return order.length() == indeg.size() ? order.toString() : "";
20}

Live state

0 constraints0 letters placed

words

letters

abcd

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L4	words=4 letters=abcd	4 words use the letters a b c d. Two neighbouring words reveal at most one rule: the first position where they differ.
2	L9	a=abc b=abd position=2	"abc" before "abd": they first differ at position 2, so c comes before d.
3	L9	a=abd b=bc position=0	"abd" before "bc": they first differ at position 0, so a comes before b.
4	L9	a=bc b=bd position=1	"bc" before "bd": they first differ at position 1, so c comes before d (already known).
5	L13	constraints=2	Now run Kahn's algorithm on the letters. Ready letters (nothing must precede them): a c.
6	L17	letter=a order=a	Place a. Letters that were waiting only for it become ready.
7	L17	letter=b order=ab	Place b. Letters that were waiting only for it become ready.
8	L17	letter=c order=abc	Place c. Letters that were waiting only for it become ready.
9	L17	letter=d order=abcd	Place d. Letters that were waiting only for it become ready.
10	L20	return=abcd	Letter order: abcd. Letters never compared with each other may be placed in any order that keeps the rules; here ties go to the smaller letter.

34.03.5

Package dependencies

To install a package you first need its dependencies, then theirs. A DFS from the requested package that appends each package *after* its dependencies finish produces an install order that contains only the packages actually needed. A package that is reached again while still on the recursion stack means a circular dependency.

This is the finish-order method from before, started from one root instead of every vertex. Packages already installed or already visited are skipped, so a shared dependency is installed once.

Java

1static List<String> installPlan(String target, Map<String, List<String>> deps) {   // dependencies first; null on a cycle
2    List<String> plan = new ArrayList<>();
3    Map<String, Integer> state = new HashMap<>();           // absent: new, 1: being resolved, 2: done
4    return resolve(target, deps, state, plan) ? plan : null;
5}
6static boolean resolve(String pkg, Map<String, List<String>> deps, Map<String, Integer> state, List<String> plan) {
7    int s = state.getOrDefault(pkg, 0);
8    if (s == 2) return true;
9    if (s == 1) return false;                               // back to a package still being resolved: circular
10    state.put(pkg, 1);
11    for (String d : deps.getOrDefault(pkg, List.of()))
12        if (!resolve(d, deps, state, plan)) return false;
13    state.put(pkg, 2);
14    plan.add(pkg);                                          // all of its dependencies are already in the plan
15    return true;
16}

Topological sort: Kahn's algorithm and reversed DFS finish order

Interactive · edit the input

directed graph · 6 vertices · 6 edges

in=2

in=1

in=0

Being processedIn-degree 0 (ready)Placed in the orderFinishedOn a cycle (never ready)

queue (front first)

in-degree

order

none yet

Setup

Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].

Step 1 / 14

Java

1List<Integer> kahn(List<List<Integer>> g) {      // topological order; shorter than n on a cycle
2    int n = g.size(); int[] indeg = new int[n];
3    for (List<Integer> out : g) for (int v : out) indeg[v]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // sources are ready
6    List<Integer> order = new ArrayList<>();
7    while (!q.isEmpty()) {
8        int u = q.poll(); order.add(u);
9        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // remove u's arrows
10    }
11    return order;                                // order.size() < n: a cycle remains
12}
13List<Integer> dfsOrder(List<List<Integer>> g) {  // reversed DFS finish order; null on a cycle
14    int n = g.size(); int[] colour = new int[n];
15    Deque<Integer> post = new ArrayDeque<>();
16    for (int s = 0; s < n; s++) if (colour[s] == 0 && !visit(g, s, colour, post)) return null;
17    return new ArrayList<>(post);
18}
19boolean visit(List<List<Integer>> g, int u, int[] colour, Deque<Integer> post) {
20    colour[u] = 1;
21    for (int v : g.get(u)) {
22        if (colour[v] == 1) return false;        // an arrow back into the stack: a cycle
23        if (colour[v] == 0 && !visit(g, v, colour, post)) return false;
24    }
25    colour[u] = 2; post.addFirst(u);             // finished after everything it points to
26    return true;
27}

Live state

0 vertices placed0 arrows removed

sources

[4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	sources=[4, 5]	Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].
2	L8	u=4 order=[4]	Take 4 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
3	L9	u=4 v=0 indeg[v]=1	4 → 0: in-degree of 0 drops to 1.
4	L9	u=4 v=1 indeg[v]=1	4 → 1: in-degree of 1 drops to 1.
5	L8	u=5 order=[4, 5]	Take 5 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
6	L9	u=5 v=2 indeg[v]=0	5 → 2: in-degree of 2 drops to 0, so 2 is ready and joins the queue.
7	L9	u=5 v=0 indeg[v]=0	5 → 0: in-degree of 0 drops to 0, so 0 is ready and joins the queue.
8	L8	u=2 order=[4, 5, 2]	Take 2 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
9	L9	u=2 v=3 indeg[v]=0	2 → 3: in-degree of 3 drops to 0, so 3 is ready and joins the queue.
10	L8	u=0 order=[4, 5, 2, 0]	Take 0 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
11	L8	u=3 order=[4, 5, 2, 0, 3]	Take 3 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
12	L9	u=3 v=1 indeg[v]=0	3 → 1: in-degree of 1 drops to 0, so 1 is ready and joins the queue.
13	L8	u=1 order=[4, 5, 2, 0, 3, 1]	Take 1 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
14	L11	return=[4, 5, 2, 0, 3, 1]	Topological order: 4 → 5 → 2 → 0 → 3 → 1. All 6 vertices were placed, which also proves the graph is acyclic. Every arrow goes from an earlier vertex to a later one.

Practice ladder

Now try it yourself

Easy

Find the Town Judge

Medium

Course Schedule
Course Schedule II
Parallel Courses III
Alien Dictionary

Advanced

Build a Matrix With Conditions
Longest Increasing Path in a Matrix

Key takeaways

A prerequisite pair (a needs b) is the arrow b to a: draw the arrow from what must come first.
No valid order means a cycle: report it instead of looping.
Alien dictionary: the first differing letter of each neighbouring pair gives one arrow; a longer word before its own prefix is invalid.
With durations, the finish time of a task is its duration plus its slowest prerequisite; the longest chain decides the total.