topological sort
A topological sort takes a directed acyclic graph (DAG) and lays its vertices out in a line so that every edge points forward — if there is an edge from A to B, then A comes before B in the ordering. The everyday meaning is dependency resolution: 'do this before that.' Putting on socks must come before shoes; a university course has prerequisites; a build system must compile a library before the program that uses it.
It only works on a DAG: the graph must be directed (the arrows say what must precede what) and acyclic (no cycles). A cycle would mean A must come before B which must come before A — an impossible, contradictory requirement, so no valid ordering exists. There is usually more than one correct topological order, since items with no dependency between them can appear in either relative position.
Two standard methods both run in O(V + E). Kahn's algorithm repeatedly removes any vertex with no remaining incoming edges (no unmet dependencies) and outputs it. The DFS method runs a depth-first search and outputs each vertex when its recursion finishes, then reverses the list. Either way you get a valid execution order — and if no ordering can be produced, that itself proves the graph contained a cycle.
queue<int> q;
for (int v = 0; v < n; ++v)
if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
for (int nb : adj[v])
if (--indeg[nb] == 0) q.push(nb);
}Each removed vertex 'frees' its successors by lowering their in-degree.
Topological sort is defined only for DAGs. Failing to produce a full ordering is the standard way to detect a cycle in a directed graph.