Topological sort

Topological sort puts the vertices of a directed graph in a row so that every edge goes from an earlier vertex to a later one, like tasks ordered so that each comes after the tasks it waits for. It runs in O(n + m) and tells you when a cycle makes such an order impossible. In a graph without cycles, the same order gives shortest and longest paths in one pass.

Explanation

A small project has 6 tasks. An arrow from one task to another means that the first task must be finished before the second can start. Here every task except task 1 waits for exactly one other task. Finish task 1, then the tasks its arrows lead to, and so on: task 1, then tasks 2 and 3, then tasks 4, 5 and 6. This is the order of breadth-first search. Any task reached this way is ready, because its only arrow comes from a task that is already finished.

Fig. 1. Every task but the first waits for one other. As soon as that one is finished, the task can start.

In a real project a task often waits for several others. In this one, task 4 can't start before tasks 2, 3 and 5 are all finished, and task 7 waits for tasks 6 and 8. When can task 4 be finished?

Fig. 2. An arrow means "finish this task first". Task 4 waits for three tasks.

Start at task 1 and finish each task as soon as an arrow leads to it from a finished task. This finishes task 1, then tasks 2 and 3, and then task 4, because an arrow leads to it from task 2. But task 5 isn't finished yet, and task 4 must wait for it. In this order, the arrow from task 5 to task 4 points backwards. Task 8 is never finished at all, because no arrow leads to it.

Fig. 3. Task 4 is reached from task 2 and finished 4th, but task 5 isn't finished: the red arrow points backwards.

Going deep is no better. Keep following the first arrow and you go from task 1 to task 2 and then to task 4, before tasks 3 and 5 are finished.

A task is ready only when every arrow into it comes from a finished task. To know when that happens, write next to each task the number of tasks it still waits for: task 4 gets 3, task 7 gets 2, and tasks 1 and 8 get 0. A task with 0 is ready. Keep the ready tasks in a line, a queue. Take the task at the front and finish it, then lower by 1 the number of every task its arrows lead to. A task whose number drops to 0 joins the queue.

An order in which every arrow goes forward is a topological order, and finding one is called topological sort. The method above is Kahn's algorithm.

Here is Kahn's algorithm on the project.

Each task shows how many tasks it waits for. Tasks 1 and 8 wait for none, so they start in the queue.

Task 1 is taken from the front of the queue and finished.

The arrow from task 1 lowers the number of task 2 from 1 to 0. Task 2 joins the queue.

The arrow from task 1 lowers the number of task 3 from 1 to 0. Task 3 joins the queue.

Task 8 is taken from the front of the queue and finished.

The arrow from task 8 lowers the number of task 7 from 2 to 1.

Task 2 is taken from the front of the queue and finished.

The arrow from task 2 lowers the number of task 4 from 3 to 2.

The arrow from task 2 lowers the number of task 5 from 1 to 0. Task 5 joins the queue.

Task 3 is taken from the front of the queue and finished.

The arrow from task 3 lowers the number of task 4 from 2 to 1.

The arrow from task 3 lowers the number of task 6 from 2 to 1.

Task 5 is taken from the front of the queue and finished.

The arrow from task 5 lowers the number of task 4 from 1 to 0. Task 4 joins the queue.

Task 4 is taken from the front of the queue and finished.

The arrow from task 4 lowers the number of task 6 from 1 to 0. Task 6 joins the queue.

Task 6 is taken from the front of the queue and finished.

The arrow from task 6 lowers the number of task 7 from 1 to 0. Task 7 joins the queue.

Task 7 is taken from the front of the queue and finished.

The queue is empty, and all 8 tasks are finished in the order 1 8 2 3 5 4 6 7.

1/20

Fig. 4. Step through Kahn's algorithm with the buttons. The number on a task is how many unfinished tasks it waits for. Green tasks are finished, light blue tasks wait in the queue.

In this order all 10 arrows point forward. This project has 21 valid orders.

Without an order: cycles

Turn one arrow around, so that task 6 must be finished before task 3. Task 3 waits for task 6, task 6 waits for task 4, and task 4 waits for task 3. None of the three can go first, so their numbers never reach 0. Kahn's algorithm finishes tasks 1, 8, 2 and 5, and then the queue is empty with 4 tasks left. Task 7 is stuck too, because it waits for task 6.

Fig. 5. Tasks 3, 4 and 6 wait for each other along the red loop, so their numbers never reach 0.

A path along the arrows that comes back to where it started is a cycle. If the graph has a cycle, no topological order exists, and a cycle is also the only reason why Kahn's algorithm can stop early (the correctness proof shows why). If fewer tasks are finished than there are tasks, there is a cycle.

The DFS method

Run depth-first search along the arrows, starting from every task that isn't visited yet: here from task 1, then from task 8. The call for a task returns only after the calls for all tasks its arrows lead to have returned. So in the order the calls return, every arrow points backwards. Reversed, it is a topological order, different from Kahn's.

Task 1 is the first task not visited yet, so a search starts there, and 1 joins the current route.

Task 2 is not visited yet, so the call for task 1 calls task 2, and 2 joins the current route.

Task 4 is not visited yet, so the call for task 2 calls task 4, and 4 joins the current route.

Task 6 is not visited yet, so the call for task 4 calls task 6, and 6 joins the current route.

Task 7 is not visited yet, so the call for task 6 calls task 7, and 7 joins the current route.

Every arrow out of task 7 is checked, so the call for task 7 returns. The return order is now 7.

Every arrow out of task 6 is checked, so the call for task 6 returns. The return order is now 7 6.

Every arrow out of task 4 is checked, so the call for task 4 returns. The return order is now 7 6 4.

Task 5 is not visited yet, so the call for task 2 calls task 5, and 5 joins the current route.

Task 4 has already returned, so the arrow from 5 to 4 needs nothing more.

Every arrow out of task 5 is checked, so the call for task 5 returns. The return order is now 7 6 4 5.

Every arrow out of task 2 is checked, so the call for task 2 returns. The return order is now 7 6 4 5 2.

Task 3 is not visited yet, so the call for task 1 calls task 3, and 3 joins the current route.

Task 4 has already returned, so the arrow from 3 to 4 needs nothing more.

Task 6 has already returned, so the arrow from 3 to 6 needs nothing more.

Every arrow out of task 3 is checked, so the call for task 3 returns. The return order is now 7 6 4 5 2 3.

Every arrow out of task 1 is checked, so the call for task 1 returns. The return order is now 7 6 4 5 2 3 1.

Task 8 is the next task not visited yet, so a search starts there, and 8 joins the current route.

Task 7 has already returned, so the arrow from 8 to 7 needs nothing more.

Every arrow out of task 8 is checked, so the call for task 8 returns. The return order is now 7 6 4 5 2 3 1 8.

Reversed, the return order 7 6 4 5 2 3 1 8 gives the topological order 8 1 3 2 5 4 6 7.

1/21

Fig. 6. Step through the DFS with the buttons. Light blue tasks are on the current route, green tasks have returned, and the boxes below list the tasks in the order their calls return. A grey arrow leads to a task that has already returned.

The calls return in the order 7 6 4 5 2 3 1 8. Every arrow points backwards in it, so reversed, 8 1 3 2 5 4 6 7 is a topological order.

Shortest and longest paths

Give each arrow a length. What is the shortest path from task 1 to task 7? Take the tasks in topological order and relax the arrows out of each one. Every arrow into a task comes from an earlier task. By the time a task is taken, all its arrows in have been relaxed from tasks whose distances were already final, so its own distance is final. Fig. 7 shows the distances after this pass.

Fig. 7. Shortest distances from task 1 after one pass in topological order. The blue path is the shortest to task 7.

In Kahn's order the distances change like this (task 8 is not reached from task 1, so it passes nothing on):

The distance of task 4 drops three times, from 7 to 5 to 4, and only then is task 4 taken. The order matters. If task 4 were taken right after task 3, its distance would still be 5, by way of task 3. It would give task 6 the distance 5 + 2 = 7. The arrow from task 5 would lower the distance of task 4 to 4 only afterwards, too late, and task 7 would end at 10 instead of 9.

The same pass finds the longest path if each relaxation keeps the larger distance: here 13, by way of tasks 3 and 6. Negative lengths are fine too, since the argument never uses the sign of a length. Dijkstra's algorithm can't do either of these, and Bellman–Ford needs up to n - 1 rounds instead of one.

Implementation

The tasks are the vertices of a directed graph, and the arrows are its edges. The number of edges into a vertex is its in-degree. Kahn's algorithm keeps in indeg[v] the number next to a task: it starts as the in-degree and drops by 1 each time a vertex with an edge to v is taken. A vertex taken from the queue is a finished task.

The graph is stored as an adjacency list: adj[u] lists the vertices that edges from u lead to. The vertices taken go into the array order. The queue works like the one in BFS, but a vertex is pushed when its last edge in is removed, not its first.

1. Initialise: count indeg[v] for every vertex; push every vertex with indeg[v] == 0.

2. Take the next vertex v from the front of the queue and append it to order.

3. Expand its edges: for each edge from v to u, lower indeg[u] by 1; if it reaches 0, push u.

4. Stop when the queue is empty.

5. Check for a cycle: if fewer than n vertices were taken, there is a cycle and no order.

The program reads n and m, then m lines u v: an edge from u to v. Vertices are numbered from 1 to n. The program prints a topological order, or -1 if there is none. For the project in Fig. 2 the input is:

8 10
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 4
6 7
8 7

The comments name the steps above.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

    // initialise
    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) q.push(v);
    }

    vector<int> order;
    while (!q.empty()) {          // stop: when the queue is empty
        // take the next vertex
        int v = q.front();
        q.pop();
        order.push_back(v);

        // expand its edges
        for (int u : adj[v]) {
            indeg[u]--;
            if (indeg[u] == 0) q.push(u);
        }
    }

    // check for a cycle
    if ((int)order.size() < n) {
        cout << -1 << '\n';
        return 0;
    }
    for (int i = 0; i < n; i++) {
        cout << order[i] << (i + 1 < n ? ' ' : '\n');
    }
}

Each vertex is pushed and taken once and each edge lowers one indeg value once, so the time is O(n + m), and the memory is O(n + m) for the adjacency list, indeg, the queue and the order. The DFS version and the pass for paths have the same bounds.

Smallest and unique orders

Some problems ask for the smallest order, comparing the vertex numbers from the left. Use a priority queue instead of the queue, so that each step takes the smallest vertex that may come next. On the project in Fig. 2 this gives 1 2 3 5 4 6 8 7, while the queue gives 1 8 2 3 5 4 6 7. Each push and take now costs O(\log n), so the time is O((n + m) \log n).

At every step the queue holds exactly the vertices that may come next. So if all n vertices are taken, the order is unique exactly when the queue never holds two vertices at once. On the project in Fig. 2 the queue starts with 1 and 8, so the order is not unique.

DFS version

To tell a cycle apart from an edge to a vertex whose call has already returned, each vertex has one of three states in state[v]: 0 if it is not visited, 1 while its call is running (it is on the current route), 2 when its call has returned. dfs(v) sets state 1 on entry, checks its edges, and on return sets state 2 and appends v to order. An edge to a vertex in state 1 leads back into the current route, so it closes a cycle. An edge to a vertex in state 2 is fine, as Fig. 8 shows.

Fig. 8. Light blue vertices are on the current route (state 1), green ones have returned (state 2), plain ones are not visited (state 0). Left: an edge to a vertex that has returned. Right: an edge back into the current route closes a cycle.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<int> state;   // 0: not visited, 1: on the current route, 2: returned
vector<int> order;
bool cycle = false;

void dfs(int v) {
    // mark it: v is on the current route
    state[v] = 1;

    // expand its edges
    for (int u : adj[v]) {
        if (state[u] == 0) {
            dfs(u);
        } else if (state[u] == 1) {
            cycle = true;  // the edge leads back into the current route
        }
    }

    // walk back: dfs(v) returns
    state[v] = 2;
    order.push_back(v);
}

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

    // initialise
    state.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        if (state[v] == 0) dfs(v);
    }

    if (cycle) {
        cout << -1 << '\n';
        return 0;
    }
    reverse(order.begin(), order.end());
    for (int i = 0; i < n; i++) {
        cout << order[i] << (i + 1 < n ? ' ' : '\n');
    }
}

On the project in Fig. 2 it prints 8 1 3 2 5 4 6 7. With the edge from 6 to 3 it prints -1 (Fig. 8, right).

Paths in a graph without cycles

Each edge now has a length w, read as a third number on its line, so adj becomes vector<vector<pair<int, long long>>> and holds pairs (vertex, length). First find order with Kahn's algorithm, and stop with no answer if it has fewer than n vertices; in its loop, read the pair as for (auto [u, w] : adj[v]) and ignore w. Then d[v] is the shortest distance from the start s (here s = 1), with d[s] = 0 and d[v] = INF for the others. Go through order and relax every edge from v to u of each vertex: if d[v] + w < d[u], set d[u] = d[v] + w.

const long long INF = 1e18;
vector<long long> d(n + 1, INF);
d[s] = 0;
for (int v : order) {
    if (d[v] == INF) continue;              // not reached from s
    for (auto [u, w] : adj[v]) {
        if (d[v] + w < d[u]) d[u] = d[v] + w;   // relax the edge
    }
}

The skip matters when lengths can be negative: without it, an edge of length -3 out of an unreached vertex would give 10^{18} - 3, which is smaller than INF and looks like a real distance. For the lengths in Fig. 7 and s = 1, the distances to vertices 1 to 8 are 0, 2, 4, 4, 3, 6, 9 and INF.

For the longest paths, start every d[v] at -INF instead, skip vertices with d[v] == -INF, and relax with d[v] + w > d[u]. Vertex 8, which can't be reached from vertex 1, stays at -INF.

Correctness proof

Kahn's algorithm keeps this invariant: \text{indeg}_v is the number of edges into $v$ from vertices not yet taken. It holds at the start, and taking a vertex lowers \text{indeg}_u by exactly 1 for each edge to $u$. A vertex is pushed only when \text{indeg}_v = 0, so every edge into it comes from a vertex taken earlier. In the order, every edge goes forward.

Now suppose the queue is empty and some vertices are left. Each of them has \text{indeg}_v \ge 1, so it has an edge in from another vertex that is left. Start at any of them and keep following such edges backwards. There are finitely many vertices, so this repeats a vertex, and the part between the two visits is a cycle. On the graph with the edge from 6 to 3, following edges backwards from vertex 7 goes to 6, 4, 3 and then 6 again, as Fig. 9 shows. And no order exists when there is a cycle: whichever vertex of the cycle comes first, the edge into it from the cycle points backwards. The answer $-1$ is right exactly when fewer than $n$ vertices are taken.

Fig. 9. Every stuck task waits for another stuck task. Following these arrows backwards must repeat a task, so there is a cycle.

For the DFS method, take an edge u \to v and look at the moment dfs(u) checks it. If $v$ is not visited, dfs(v) is called and returns before dfs(u) does. If $v$ has returned, it returned before dfs(u). If $v$ is on the current route, there is a path along the edges from $v$ to $u$, and with the edge u \to v it forms a cycle. In a graph without cycles, then, $v$ always returns before $u$, and in the reversed return order $u$ comes before $v$.

If the graph has a cycle, the program does report it. Let $v$ be the first vertex of the cycle that DFS visits, and $u$ the vertex before it on the cycle. Before dfs(v) returns, every vertex that can be reached from $v$ is visited, including $u$. So dfs(u) runs while $v$ is still on the current route, and the edge u \to v sets the flag.

Common mistakes

• Ordering vertices by when a search first reaches them, which can put a task before one it waits for, as in Fig. 3. Use the in-degree counts or the reversed return order.

• Printing the DFS return order without reversing it, so every edge points backwards, or starting DFS only from vertex 1, so vertices like 8 are left out. Reverse the list, and loop over all vertices.

• Detecting a cycle in DFS with a single "marked" flag, which calls an edge to a returned vertex, such as the edge from 5 to 4, a cycle. Use three states, and report only an edge to a vertex on the current route.

• Forgetting the cycle check in Kahn's algorithm, so a partial order is printed as if it were the answer. Compare the number of vertices taken with $n$ and print $-1$ when it is smaller.

Similar algorithms

Cycle detection is the tool when the question is only whether there is a cycle, or the task is to print one. It is a DFS with the same three states.

When the graph has cycles, there is no topological order to relax the edges in. Then shortest paths need Dijkstra's algorithm, in O((n + m) \log m) if no edge is negative, or Bellman–Ford if some are.

In dynamic programming, the states and the states each one depends on form a graph without cycles, and the order in which the states are computed is a topological order.

Strongly connected components help when the graph has cycles: each component becomes one vertex, and the resulting graph has no cycles and can be sorted.

Practice