Topological sort in Python

Why it matters

Many real jobs depend on other jobs. A build tool must compile a library before the program that uses it. A spreadsheet must calculate cell A1 before cell B1 when B1 is =A1 * 2. A university will not let you take Data Structures before Programming, and it will not let you take Compilers before Data Structures either. Each of these asks for an order of tasks that respects every dependency. The name for that order is a topological sort, and this lesson shows you how to build one in Python, how to tell when one is impossible, and how to use the order to answer longer questions.

Lesson 2 gave you depth-first search, and the cycle rules from that lesson come back here. Topological sort is the bridge between "is there a loop?" and "in what order do I do things?"

The idea: getting dressed

Think about getting dressed in the morning. Your socks go on before your shoes. Your shirt goes on before your jacket. Those are rules: one item must come before another. But the rules do not decide everything. You can put on your watch before or after your socks, because no rule says otherwise. So there is more than one valid order, and any of them is fine as long as every rule holds.

A topological sort is exactly that. You have a set of things and a set of rules of the form "A before B". Your job is to list all the things in one order where every rule holds.

In graph language, each thing is a vertex, and each rule A before B is a directed edge from A to B. The arrow points forward in time. A topological order is a list of all the vertices such that, for every edge from u to v, the vertex u appears somewhere before v in the list.

Two terms are needed here. A directed acyclic graph, usually shortened to DAG, is a directed graph with no cycle. "Acyclic" means "no cycle", and a cycle in a directed graph is a path that follows arrows and comes back to its start. A topological order exists only for a DAG. That is the whole reason cycles matter in this lesson.

Why a cycle breaks everything

Suppose the rules are: A before B, B before C and C before A. Start anywhere in the list. If you put A first, then B must come after A, and C after B, but the rule C before A says C must come before A. There is no place to put C. The same problem appears with any starting point, because the rules form a loop of "before" with no beginning.

This is the simplest proof that a cycle makes an order impossible. If a cycle exists, no topological order exists, and a good algorithm must notice this and report it. Most algorithms in this lesson do exactly that: they return an order when the graph is a DAG, and report a problem when it is not.

Kahn's algorithm: start with the things that have no rules left

The first method is named after Arthur Kahn, who described it in 1962. It works like a checklist. At each step, you find the tasks that have no unmet prerequisites, do them, and cross them off. Crossing off a task may free up other tasks, which then become ready.

To make this precise, define the indegree of a vertex as the number of edges pointing into it. The indegree counts the unmet prerequisites. A vertex with indegree 0 has no rule left that blocks it, so it can go next.

The steps are:

1. Compute the indegree of every vertex. Walk through all edges and add one to the indegree of each edge's target.
2. Put every vertex with indegree 0 into a queue.
3. Take the vertex at the front of the queue. Add it to the result list. For each edge from it to a neighbour, subtract one from the neighbour's indegree. If the neighbour's indegree becomes 0, add it to the back of the queue.
4. Repeat step 3 until the queue is empty.
5. If the result list holds all V vertices, you have a topological order. If it holds fewer, the leftover vertices are stuck on a cycle, so no order exists.

The queue is the same first-in, first-out line from lesson 1. In Python, the right tool for it is collections.deque. A deque is a list that is fast at both ends: append adds to the back and popleft removes from the front. A plain list also works, but list.pop(0) must move every other item one place to the left, which gets slow for large inputs. The vertices come out in the order they became ready, and that order is one valid answer.

The time is O(V + E). Computing indegrees reads every edge once. Each vertex enters the queue once and each of its edges is used once to reduce a neighbour's indegree. The space is O(V + E) for the adjacency list and O(V) for the indegree list and queue.

Worked example, step by step

Take six vertices numbered 0 to 5 and six edges: 5 to 2, 5 to 0, 4 to 0, 4 to 1, 2 to 3, and 3 to 1. Read each edge as "the first must come before the second". This graph is used in several programs below, and the final order is 4, 5, 2, 0, 3, 1.

First compute the indegrees. Vertex 0 has two incoming edges (from 5 and from 4), so its indegree is 2. Vertex 1 has two incoming edges (from 4 and from 3), so 2. Vertex 2 has one (from 5), so 1. Vertex 3 has one (from 2), so 1. Vertices 4 and 5 have none, so 0.

The queue starts with the vertices of indegree 0, in index order: 4 and 5. Here is the trace, one row per pop. The indegree column shows the values after the step.

The result is 4, 5, 2, 0, 3, 1. The queue order gives each vertex only after its prerequisites are done. Check it against the edges: 4 is before 0 and 1, 5 is before 2 and 0, 2 is before 3, and 3 is before 1. All six edges point forward.

Watch the queue in the animation below. Each row you saw above is one step of the animation. Pay attention to when a vertex joins the back of the queue: it joins at the moment its last prerequisite is removed, not before.

Why the queue order is always valid

It is worth proving to yourself that the order Kahn's algorithm produces is valid, because the proof is short and it shows what the queue is for. Take any edge from u to v. The vertex v enters the queue only when its indegree reaches 0. That indegree counts the edges into v, and the edge from u is one of them. So v cannot enter the queue until the edge from u has been removed. The edge is removed only when u is taken from the queue and added to the result. Therefore u appears in the result before v does.

Here is the same idea with numbers from the worked example. Vertex 3 has one incoming edge, from 2. Its indegree stays at 1 until vertex 2 is taken out of the queue. Only then does 3 join the queue. Vertex 2 is in the result before vertex 3, as the edge requires. Nothing else could have put 3 earlier, because nothing else points to 3.

The same argument explains the cycle check. Suppose a cycle exists. The first vertex of the cycle to leave the queue would need its predecessor on the cycle to have left first. That predecessor needs its own predecessor to have left, and so on around the loop. No vertex on the cycle can go first, so none of them ever enters the queue. The result is missing vertices, and the count shows it.

Program 1: Kahn's algorithm in Python

Here is the algorithm as a complete program. It reads the number of vertices and edges, then the edges, and prints the order. If the graph has a cycle, it prints cycle.

Type this into the Input box:

6 6
5 2
5 0
4 0
4 1
2 3
3 1

Expected output:

order: 4 5 2 0 3 1

The program matches the table row by row. The line indegree[v] -= 1 is the "cross it off" step: removing a prerequisite lowers the count of the vertex that was waiting for it. The test if indegree[v] == 0 adds the vertex at the exact moment its count reaches zero, so it is never added twice. Each vertex reaches zero exactly once, which is why the queue cannot hold duplicates.

The line deque(v for v in range(n) if indegree[v] == 0) builds the first queue in one step. The part inside the brackets is a generator expression. It produces the numbers one at a time without building a separate list first.

The cycle test is len(order) < n. The order list ends with exactly as many items as vertices that were placed. A vertex on a cycle never reaches indegree 0, because one of its prerequisites is also on the cycle and never gets removed. It therefore never enters the queue, and the length of order ends below n. This check is the entire cycle detection. You do not need a separate cycle search.

Now test the cycle. Type this input, which has the cycle 0 to 1 to 2 back to 0, and check that you see cycle:

3 3
0 1
1 2
2 0

Every vertex on that cycle has indegree 1, so the queue starts empty, order stays empty, and the program prints cycle.

Program 2: can all courses be finished?

A classic interview question has a yes or no answer: can a student take every course, given the prerequisite rules? The answer is yes exactly when the prerequisite graph is a DAG. Kahn's algorithm answers it directly: if the count of taken courses reaches n, every course can be taken in some order.

The program below reads the courses and rules, using the same format as Program 1, and prints yes or no. A rule a b means course a must be taken before course b.

Type this input, which is a chain of four courses, and press Run:

4 3
0 1
1 2
2 3

Expected output:

yes

Change the input to make a loop by adding the rule 3 0 after the three rules, and change the first line to 4 4. Now course 1 needs 0, course 2 needs 1, course 3 needs 2, and course 0 needs 3. Nobody in the loop can start first, so the answer is no. Try it to see the program print no.

Notice that the program never needs to know the actual order to answer the question. The count of taken courses is enough. This is a useful habit in interviews: if a question asks "is it possible?", you often do not need to build the answer, only to check that the algorithm finishes.

Depth-first topological sort

Kahn's algorithm works from the front: it starts with what is ready. The second method works from the back, using the depth-first search from lesson 2. The key fact is this: when a DFS finishes a vertex, every vertex reachable from it has already finished. So a vertex finishes only after everything that depends on it. If you record vertices in finish order and read the list backwards, each vertex comes before everything it points to.

Concretely, run DFS from each unseen vertex. When a vertex's loop over its neighbours ends, append it to a list. When the whole run is done, the list holds the vertices in finish order, with the last-finished one at the end. Read the list from the end back to the start, and you have a topological order. Python's reversed function does the reading from the end.

The cycle check is the three-state rule from lesson 2. If the walk looks at a neighbour whose state is 1 (on the current path), the graph has a cycle.

Why does reversing the finish order work? Take any edge u to v. When the walk is at u, there are two cases. If v is unseen, the walk visits v inside u's loop, so v finishes before u. If v is already finished, it finished before u as well. A neighbour still on the current path would mean a cycle, which the check reports. In every case v finishes before u, so v is in the list before u. Read the list backwards, and u comes before v, as the edge requires.

The stack animation below shows vertices being added in finish order. Watch the first vertex that goes on the list: it is always one with no outgoing edges, because it finishes before anything else in its walk.

Program 3 implements this. It reads the same six-vertex graph as Program 1. The function dfs returns True when it finds a cycle somewhere below the vertex it is working on. The result is passed back up with return rather than kept in a global variable.

Type the six-vertex input from Program 1 into the Input box to run this one too. The expected output is:

order: 5 4 2 3 1 0

Check the order against the edges. Vertex 5 is first, and it points to 2 and 0, which both come after it. Vertex 4 points to 0 and 1, both later. Vertex 2 points to 3, later. Vertex 3 points to 1, later. Every edge points forward, so the order is valid. It is not the same as Kahn's order, and that is expected: several valid answers exist.

Two details in the code deserve a second look. The line finished.append(u) runs after the loop, so a vertex is added only when everything it leads to has already been added. The line reversed(finished) reads the list from its last item to its first, so the printed order starts with 5, the last vertex to be added. If you print finished without reversed, you get order: 0 1 3 2 4 5. That is not valid: 5 must come before 2, but 2 is printed first.

The outer loop for s in range(n) starts a walk from every unseen vertex, exactly as in lesson 2. A topological sort must cover every vertex, including those with no edges at all.

Program 4: longest chain in a DAG

A topological order makes many path problems easy. Suppose each task takes one day, and the tasks depend on one another. How many days is the longest chain of tasks that must happen one after another? That is the longest path in a DAG, and it has a neat solution. Process the vertices in topological order. For each vertex, look at its outgoing edges and push the best chain length forward to each neighbour.

Why does processing in topological order work? When you reach a vertex, every edge into it has already been processed, because its prerequisites came earlier. So the best chain length to that vertex is final when you read it, and you can safely pass it on.

Program 4 uses Kahn's order from Program 1 and then computes, for each vertex, the length of the longest chain ending there. The input is the same six-vertex graph.

Expected output:

longest path to each vertex: [1, 3, 1, 2, 0, 0]
longest chain: 3

Read the list for each vertex. Vertex 1 has longest 3, which is the chain 5, 2, 3, 1 with three edges. Vertex 0 has 1, because the edges 4 to 0 and 5 to 0 each give a chain of one edge. Vertices 4 and 5 have 0, since nothing points to them.

The update line is the heart of the method. longest[v] = max(longest[v], longest[u] + 1) says: a chain ending at v can be extended by the edge from u, giving one more edge than the best chain ending at u. The built-in max keeps the best of the chains coming in from different predecessors. The last line uses max on the whole list to find the longest chain overall.

This pattern is a special case of dynamic programming, the technique you will meet in module 26. The idea is the same: a value for each vertex depends on values of earlier vertices, and a good order computes each one once.

Program 5: the smallest valid order

Kahn's algorithm gives one valid order, and the order depends on how the queue is kept. A queue returns the vertices in the order they became ready, which is not always the smallest order. Many judges ask for the order that is smallest when read as numbers, so the answer is unique. The fix is to replace the queue with a min-heap. A heap is a structure that always gives back the smallest item it holds. Python's heapq module keeps a plain list in heap order. heapq.heappush adds an item, heapq.heappop removes the smallest one, and heapq.heapify turns an existing list into a heap in one step. Each time you need a ready vertex, you take the smallest number that is ready.

The swap is small. The code is Program 1 with a heap in place of the deque. The heap keeps the ready vertices in order, so heappop always returns the smallest.

Type this input and press Run. The graph has three rules, 4 before 0, 3 before 1 and 2 before 1:

5 3
4 0
3 1
2 1

Expected output:

smallest order: 2 3 1 4 0

Compare with what a plain queue would give on this input. The queue starts with 2, 3 and 4. It takes 2, then 3, which frees 1, and 1 joins the back behind 4. So the queue gives 2, 3, 4, 1, 0. The heap, however, always picks the smallest ready vertex. After 2 and 3 are taken, the ready set is {1, 4}, and the heap picks 1 before 4. The result is 2, 3, 1, 4, 0, which is smaller when compared number by number.

The cost of the heap is a log factor. Each push and pop costs O(log V), so the total time is O((V + E) log V). For inputs with a few thousand vertices this is fast, and it is the price of a unique answer.

Complexity

Kahn's algorithm: O(V + E) time, O(V + E) space. DFS-based topological sort: the same time and space, plus the recursion depth, which can reach V on a long chain and then hits Python's recursion limit of 1000 by default. The smallest-first version: O((V + E) log V) time. The longest-path version adds no extra cost to Kahn's algorithm, because it reads the same edges.

The sort itself is linear in the size of the graph, which is why it is the method of choice for large dependency graphs such as a build of a large software project.

A second example with a cycle inside a bigger graph

The six-vertex example always produced a full order, so it did not show the cycle check at work. Take a graph where most vertices are fine, but three of them form a loop. There are six vertices, numbered 0 to 5, and six edges: 0 to 1, 1 to 2, 2 to 3, 3 to 1, 0 to 4 and 4 to 5. The vertices 1, 2 and 3 form the cycle 1 to 2 to 3 and back to 1. The other vertices are not on the cycle.

Start with the indegrees. Vertex 0 has 0. Vertex 1 has 2, from 0 and from 3. Vertex 2 has 1, from 1. Vertex 3 has 1, from 2. Vertex 4 has 1, from 0. Vertex 5 has 1, from 4. The queue starts as [0].

Pop 0 and add it to the result. Its edge to 1 reduces the indegree of 1 from 2 to 1, which is not yet 0, so 1 waits. Its edge to 4 reduces 4 from 1 to 0, so 4 joins the queue. Pop 4. Its edge to 5 reduces 5 to 0, so 5 joins the queue. Pop 5, which has no edges out. The queue is now empty.

The result is 0, 4, 5. That has 3 vertices, and the graph has 6. The three missing vertices are 1, 2 and 3, which are exactly the cycle. Vertex 1 is waiting for its edge from 3, but vertex 3 can only be processed after 2, and 2 only after 1. Nothing breaks the loop, so the program prints cycle.

Notice that the cycle does not stop the vertices that are not on it. Vertices 0, 4 and 5 were ordered correctly, because none of them lies on the loop. Program 1, with a line that prints order before the check, shows this partial result as partial: [0, 4, 5]. A partial result like this is useless for a build, but it tells you which part of the graph is stuck. That is exactly what you need when you debug a dependency problem.

Common mistakes and what they look like

Mistake 1: running the sort on an undirected graph. An undirected edge has no direction, so "before" has no meaning. If you store each edge in both directions, every vertex has indegree at least 1, and the queue starts empty. Kahn's algorithm then prints cycle. For this input, a path 0 - 1 - 2 stored both ways:

3 4
0 1
1 0
1 2
2 1

The program prints cycle. That is what the code does for that input, but the question itself was wrong. Check whether the problem gives directions.

Mistake 2: counting the wrong way round. The rule "a before b" must become an edge from a to b, and the indegree of b must go up. If you swap the two, you get the reverse order: the dependent task comes first. Read the edge direction in the problem twice.

Mistake 3: skipping the count check. If you never compare the result size with n, a cycle is silent. The program prints a partial order, which looks plausible but is missing vertices. Always check that len(order) == n.

Mistake 4: a vertex that never joins the queue. If you subtract the indegree but forget the if indegree[v] == 0 add, a vertex is never queued once its last prerequisite is gone. The count stays low, and the program reports cycle for a graph that has none. Put the add inside the same loop as the subtraction, so every neighbour is checked.

Mistake 5: an index error for the vertex numbers. If the problem numbers courses from 1 and you use them directly in a list of length 5, the program fails when it reaches course 5. Python stops with this message:

IndexError: list index out of range

Subtract 1 when reading, or make the lists n + 1 long.

Mistake 6: printing the finished list in the wrong order. In Program 3 the finished vertices are appended, so the list is in finish order. If you print it from the start, you get the reverse order, which is not a valid topological order. For the six-vertex graph the output is order: 0 1 3 2 4 5, where 5 is printed after 2 even though the edge 5 to 2 needs 5 first. Check one edge by hand after each change.

Mistake 7: calling poll, a Java name. A queue in Python is a deque, and the method to remove from the front is popleft. Calling poll gives this error:

AttributeError: 'collections.deque' object has no attribute 'poll'

Mistake 8: forgetting an import. Using deque without from collections import deque gives:

NameError: name 'deque' is not defined

Mistake 9: popping an empty heap. heapq.heappop raises an error when the heap is empty. This happens when a loop tries to pop more items than were pushed:

IndexError: index out of range

The while ready: check in Program 5 prevents this. Never remove it.

Debugging walkthrough

Suppose Program 1 prints cycle on an input you believe is a DAG. Work through this checklist.

First, print the indegrees after reading the edges with print(indegree). Compare them with a count you do on paper for the vertices you care about. If a vertex has the wrong number, the edges were read with the wrong direction or the wrong numbers.

Second, print the queue at the start. If it is empty, no vertex has indegree 0. That means every vertex has a prerequisite, so either the graph really has a cycle or the input is reversed. Print the edges as read to find out which.

Third, print each pop and the indegree changes. Compare the sequence with your table by hand. The first place where the program differs from your table is the bug.

Fourth, check the count. If len(order) is less than n, print the vertices that never entered the queue. They are the vertices on or downstream of a cycle, and the cycle is among them.

Variations and edge cases

Several valid answers. Most problems accept any topological order. Those that ask for a unique answer usually ask for the smallest order, which needs the heap from Program 5. Read the statement to see which kind you have.

Checking a given order. To check whether a proposed list is valid, store each vertex's position in the list, then check that for each edge u to v, the position of u is smaller than the position of v. A dictionary or a list can hold the positions. This takes O(V + E) time and is a common verification step.

A graph with no edges. Every vertex has indegree 0, so the answer is the vertices in index order. The sort works without a special case.

A single vertex and no edges. The answer is just that vertex.

Duplicate edges. A repeated edge adds 1 to the indegree twice and subtracts 1 twice when processed, so the sort still works. Its effect on the longest-path calculation is also harmless, because max ignores the repeat.

Multiple components. Kahn's algorithm handles them without extra code. Each component's sources enter the queue at the start.

Interview questions this lesson answers

"Given prerequisites, is there a valid order of courses?" Kahn's algorithm: the answer is yes if every vertex gets processed. O(V + E) time.

"Return any valid build order, or report that a cycle makes a build impossible." Kahn's algorithm, returning the list if its length equals V and an error otherwise.

"Return the smallest valid order." Kahn's algorithm with a min-heap instead of a queue. O((V + E) log V).

"What is the longest chain of dependent tasks?" Process vertices in topological order, and push the best length forward along each edge.

"Why does the DFS version add each vertex to the list only after its neighbours?" Because a vertex finishes only after every vertex reachable from it has finished. Reading the list from the end therefore puts each vertex before everything it points to.

Real-world uses

Build systems such as Make, Gradle and Maven use a topological order to decide which library to compile first. Spreadsheets recalculate cells in topological order, and report a circular reference when they find a cycle. Package managers install dependencies in an order that respects them. Course planners check prerequisites before showing a student a valid timetable. Each of these is the same algorithm with different labels on the vertices.

Practice

Exercise 1 (easy). Find a topological order for the edges 0 to 1, 0 to 2, 1 to 3 and 2 to 3. Hint: vertex 3 must come last, because both 1 and 2 point to it.

Show the answer

One valid order is 0, 1, 2, 3. Another is 0, 2, 1, 3. Both put 0 first, both put 3 last, and every edge points forward.

Exercise 2 (easy). Is the order 4, 5, 0, 2, 3, 1 valid for the six-vertex example? Check every edge.

Show the answer

Yes. The edges are 5 to 2 (5 before 2: yes), 5 to 0 (5 before 0: yes), 4 to 0 (yes), 4 to 1 (yes), 2 to 3 (2 before 3: yes) and 3 to 1 (3 before 1: yes). Every edge points forward.

Exercise 3 (easy). Courses 0 to 3 have the rules: 1 needs 0, 2 needs 1, 3 needs 2 and 0 needs 3. Can all four be taken? Give the reason.

Show the answer

No. The rules form the loop 0 needs 3, 3 needs 2, 2 needs 1 and 1 needs 0. Each course in the loop needs another one in the loop first, so none can start. In edge form, the rules are 0 to 1, 1 to 2, 2 to 3 and 3 to 0, which is a cycle. Kahn's algorithm would start with an empty queue and report that not all vertices can be ordered.

Exercise 4 (medium). Run Kahn's algorithm by hand on the edges 0 to 2, 1 to 2, 2 to 3, 3 to 4 and 1 to 4. List the queue after each pop. Hint: start with the vertices of indegree 0.

Show the answer

Indegrees: 0 has 0, 1 has 0, 2 has 2, 3 has 1, 4 has 2. The queue starts [0, 1]. Pop 0: 2 drops to 1, queue [1]. Pop 1: 2 drops to 0 so it is added, and 4 drops to 1. Queue [2]. Pop 2: 3 drops to 0 so it is added. Queue [3]. Pop 3: 4 drops to 0 so it is added. Queue [4]. Pop 4. Order: 0, 1, 2, 3, 4. Program 1 prints order: 0 1 2 3 4 for this input.

Exercise 5 (medium). Modify Program 1 so it prints the indegree of every vertex before the loop starts. Then explain what the first queue contains for the six-vertex example.

Show the answer

Add print(indegree) just before the queue = deque(...) line. For the six-vertex example the output is [2, 2, 1, 1, 0, 0], which means 0: 2, 1: 2, 2: 1, 3: 1, 4: 0, 5: 0. The first queue holds the vertices with indegree 0, which are 4 and 5, in index order.

Exercise 6 (medium). Explain why the cycle test len(order) < n in Program 1 catches a cycle, even though the program never looks for a cycle directly.

Show the answer

Every vertex on a cycle has at least one prerequisite on the same cycle. That prerequisite can only be removed after it is processed, which needs its own prerequisite to be removed first, and so on around the loop. None of them ever reaches indegree 0, so none enter the queue. The count of processed vertices stays below n, and that is the signal. Vertices downstream of the cycle are also never processed, so the count is low for them too.

Exercise 7 (medium). Check whether Program 3 reports cycle when a vertex is reached through an edge whose target has state 1. Then test it on the input 3 3, 0 1, 1 2, 2 0, and say what it prints.

Show the answer

The program already sets cycle = True when state[v] == 1, so it prints cycle. The walk starts at 0, marks it 1, goes to 1 (state 1), then to 2 (state 1), and from 2 the edge to 0 finds state 1, which is the cycle.

Exercise 8 (medium). Write the longest-path values for the graph with edges 0 to 1, 1 to 2, 0 to 2 and 2 to 3. Then say which edge gives the longest chain. Hint: the longest chain ends at 3.

Show the answer

Values: vertex 0 is 0, vertex 1 is 1, vertex 2 is 2 (through 0 to 1 to 2, not 0 to 2), and vertex 3 is 3. Program 4 prints longest path to each vertex: [0, 1, 2, 3] and longest chain: 3. The longest chain is 0, 1, 2, 3 with three edges. The direct edge 0 to 2 gives only 1 for vertex 2, so the max in the update keeps the longer route.

Exercise 9 (hard). Explain why the DFS-based method adds a vertex to the list only after its loop over neighbours finishes, and what would go wrong if it added on entry.

Show the answer

A vertex needs to appear after everything that depends on it, so reading the list from the end puts it before them. Adding on entry would put a vertex in the list before its neighbours, which reverses the required order. Take the single edge 2 to 3. If 2 is added on entry, the list becomes [2, 3], because the walk enters 2 first and then 3. Reading that list from the end gives 3, 2, which puts 3 before 2 and breaks the edge.

Exercise 10 (hard). Write Kahn's algorithm that returns the lexicographically smallest order, but for a graph with 200,000 vertices and 500,000 edges. Give the time complexity and explain why the heap is needed for a unique answer.

Show the answer

Use the Program 5 structure with the heap. The time is O((V + E) log V). With 200,000 vertices and 500,000 edges, the heap sees at most 200,000 pushes and 200,000 pops, each costing up to about 18 comparisons. Python runs this more slowly than a compiled language would, so measure it on your own machine before you rely on it. The heap is needed because a plain queue returns vertices in the order they became ready, which depends on the edges and on the starting order. The heap always returns the smallest ready vertex, which gives the one order that is smallest when read as numbers, so the answer is unique.

What you now know

• A topological order lists every vertex so that each edge points forward. It exists only in a DAG.
• A cycle makes a topological order impossible, and Kahn's algorithm detects it because some vertices never reach indegree 0.
• Kahn's algorithm uses indegree counts and a deque as the queue, and runs in O(V + E) time.
• The DFS method adds vertices on finish and reads the list from the end, using the three-state cycle check from lesson 2.
• A min-heap from heapq in place of the queue gives the smallest valid order, at a cost of O((V + E) log V).
• The longest path in a DAG comes from one pass over a topological order, with max at each edge.