Topological Sort (Kahn)
O(n + m)Order the vertices of a DAG so every edge points forward: repeatedly remove indegree-0 vertices with a queue. If the order comes out short, the graph has a cycle. Swap the queue for a min-heap to get the lexicographically smallest order.
// use it on
CSES: Course Schedule ↗
Print any valid course order or detect that none exists, which is this function verbatim.
// the code
// returns a topological order, or {} if the graph has a cycle
vector<int> toposort(vector<vector<int>>& adj) {
int n = adj.size();
vector<int> indeg(n, 0), order;
for (auto& nbrs : adj)
for (int v : nbrs) indeg[v]++;
queue<int> q;
for (int u = 0; u < n; u++)
if (indeg[u] == 0) q.push(u);
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>{};
}// more dags & satisfiability