whoashish's cp notes

Topological Sort

3 min read

A topological ordering of a directed graph lists the vertices so that every edge has before . It exists iff the graph is a DAG, and it is generally not unique.

Kahn’s algorithm (BFS-based)

Repeatedly remove a vertex with in-degree 0. Doubles as a cycle detector: if fewer than vertices come out, the graph has a cycle.

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

Swap the queue for a priority_queue to get the lexicographically smallest topological order — a very common problem variant.

DFS-based

Push each vertex when its subtree is finished, then reverse.

vector<int> order; vector<int> state;   // 0 = white, 1 = grey, 2 = black
bool cycle = false;
 
void dfs(int u, vector<vector<int>>& adj) {
    state[u] = 1;
    for (int v : adj[u]) {
        if (state[v] == 0) dfs(v, adj);
        else if (state[v] == 1) cycle = true;      // back edge
    }
    state[u] = 2;
    order.push_back(u);
}
 
vector<int> topoDFS(int n, vector<vector<int>>& adj) {
    state.assign(n, 0); order.clear(); cycle = false;
    for (int i = 0; i < n; i++) if (!state[i]) dfs(i, adj);
    if (cycle) return {};
    reverse(order.begin(), order.end());
    return order;
}

The three-colour scheme is the point: a grey neighbour means a back edge, hence a cycle. A black neighbour is fine — it is a forward or cross edge.

Which to use

NeedUse
Explicit cycle detectioneither — Kahn is more direct
Lexicographically smallest orderKahn with a priority queue
Avoiding deep recursionKahn
Counting the number of topological ordersDP over subsets,
Checking uniquenessKahn — unique iff the queue never holds two vertices at once
Preprocessing inside a DFS-based algorithmDFS version

What topological order unlocks

Once vertices are in topological order, any DP over a DAG becomes a single loop:

  • Longest / shortest path in a DAG — relax edges in topological order, , and negative weights are fine
  • Counting paths between two vertices
  • Reachability / transitive closure by processing in reverse order
  • Dependency resolution — build systems, course prerequisites, task scheduling
  • 2-SAT — assign values in reverse topological order of the condensation
  • DP on DAGs generally
  • A DAG has a unique topological order iff it contains a Hamiltonian path.
  • The longest path in a DAG is solvable in linear time (unlike general graphs, where it is NP-hard).
  • Mirsky’s theorem: the minimum number of antichains needed to cover a DAG equals the length of its longest chain. Computing it is exactly the longest-path DP.
  • Dilworth’s theorem: the minimum number of chains covering a poset equals the size of its largest antichain — computed via bipartite matching.

See also: Kahn’s Algorithm · Cycle Detection · Shortest Paths on DAGs

Graph View