Topological Sort
Order a DAG so every directed edge points forward, then reuse that order for dependency processing and DAG DP.
Topological Sort
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Topological sort turns a DAG into a linear order that respects every directed edge. Once that order exists, many dependency problems become ordinary left-to-right DP or greedy scans.
When to Use It
Use topological sort when:
the graph is directed and acyclic, or the task asks you to detect whether it is,
edges represent prerequisites or dependency constraints,
a DP transition only depends on earlier states.
Core Idea
In a DAG, at least one vertex has indegree zero. Remove such vertices one by one, appending them to the order and updating the indegrees of their outgoing neighbors. That is Kahn's algorithm.
Key Insight
The order is not usually unique, and that is fine. What matters is that every edge goes from earlier to later. That is exactly the condition needed to process a node after all of its prerequisites are done.
Operations / Main Technique
compute indegrees,
push all indegree-zero vertices into a queue,
repeatedly pop, output, and relax outgoing edges,
if not all vertices are output, a cycle exists.
Worked example.
If course \(A\) and \(B\) must be taken before \(C\), then edges \(A \to C\) and \(B \to C\) guarantee \(C\) appears after both of them in every topological order.
Correctness Intuition
A vertex with indegree zero has no remaining prerequisite, so placing it next cannot violate any edge constraint. When it is removed, its outgoing edges are no longer relevant to the remaining graph. Repeating this preserves correctness.
Complexity Analysis
Kahn's algorithm runs in \(O(n + m)\) time and \(O(n)\) extra memory.
Implementation
The sample returns an empty vector if the graph contains a cycle. That makes it easy to use the same routine both for ordering and for cycle detection.
Common Pitfalls
Forgetting that topological order exists only for DAGs.
Using an order-based DP without checking for cycles first.
Mixing edge direction with the dependency statement from the problem.
Variants / Extensions
DFS finishing-order topological sort.
Lexicographically smallest topological order with a priority queue.
DAG DP once the order is available.
Practice Problems
Order courses by prerequisites.
Longest path in a DAG.
Count paths in a DAG modulo a prime.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<int> topological_sort(const vector<vector<int>>& graph) {
int n = (int)graph.size();
vector<int> indeg(n, 0);
for (int v = 0; v < n; ++v) {
for (int to : graph[v]) {
++indeg[to];
}
}
queue<int> q;
for (int v = 0; v < n; ++v) {
if (indeg[v] == 0) {
q.push(v);
}
}
vector<int> order;
while (!q.empty()) {
int v = q.front();
q.pop();
order.push_back(v);
for (int to : graph[v]) {
if (--indeg[to] == 0) {
q.push(to);
}
}
}
if ((int)order.size() != n) {
return {};
}
return order;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.