uniolympiads Ελληνικά

Topological sort

An order of the vertices of a DAG in which every edge points forward, in O(n+m)O(n + m). Every DP on a DAG runs on top of it.

When

Dependencies ("course aa before bb"), or a DP on a directed acyclic graph: longest path, number of paths, anything computed from the predecessors.

The idea (Kahn)

A vertex with no incoming edges can go first. Place it, delete its edges, and some other vertices are left with no incoming edges. Keep the in-degree of every vertex and a queue of those with in-degree 0.

If at the end fewer than nn vertices have come out, the rest always have some incoming edge among themselves. So there is a cycle, and the function returns an empty vector.

DP on a DAG

In Longest Flight Route you compute the longest path from 11 to nn. Go through the vertices in topological order, so that when you reach vv all its predecessors are done:

f(v)=1+max⁡u→vf(u).f(v) = 1 + \max_{u \to v} f(u).

Game Routes is the same with a sum instead of a maximum, modulo 109+710^9 + 7.

Pitfalls

  • A topological order is not unique. If the problem wants the lexicographically smallest one, replace the queue with a priority_queue (smallest first).
  • In Longest Flight Route, vertices not reachable from 11 must not contribute. Start with f=−∞f = -\infty everywhere except f(1)=1f(1) = 1.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/topological-sort.cpp
// Topological order of a directed graph (Kahn's algorithm). O(n + m).
// Returns an empty vector if the graph has a cycle.

vector<int> topologicalSort(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indeg[v]++;
        }
    }
    queue<int> q;
    for (int u = 0; u < n; u++) {
        if (indeg[u] == 0) {
            q.push(u);
        }
    }
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    if ((int)order.size() < n) {
        return {};
    }
    return order;
}

Tested on 2,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.