The shape of the question#
"You must take A before B" is an edge from A to B. A list of such rules is a directed graph, and the question "can I finish everything" is the question "does this graph have a cycle".
If A must come before B, and B before C, and C before A, then nothing can go first. That is the only way to fail, and every failure looks like that.
Kahn's algorithm, counted in#
For each node, count how many prerequisites it has. That is its in-degree.
- Every node with in-degree 0 can be done right now. Put them all in a queue.
- Take one out. That is the next item in the order.
- For each node that depended on it, reduce that node's in-degree by one. If it drops to 0, it is now unblocked, so push it.
- Repeat until the queue is empty.
If you produced every node, you have a valid order. If the queue ran dry with nodes left over, those nodes are in a cycle: each was still waiting for another one that was also waiting.
That last line is the useful part. You do not need a separate cycle detector. Counting how many nodes you emitted tells you.
Building the graph#
Adjacency lists, not a matrix. With 100000 nodes a matrix is 10 billion cells, and the list is the size of the input. For each rule "B needs A", store B in A's list and add one to B's in-degree. Getting the direction backwards is the single most common bug here, so write down what an edge means before you write the loop.
The cost#
- Time:
O(V + E). Every node enters the queue at most once, and every edge is looked at once. - Memory:
O(V + E)for the lists and the counts.
The other way to do it#
Depth first search with three colours (unvisited, in progress, finished) finds cycles too: reaching a node that is still in progress means you have gone round in a circle. It is just as good. Kahn's version is easier to get right under pressure because there is no recursion to blow the stack on a long chain.
Where this shows up#
Build systems deciding what to compile, package managers resolving dependencies, spreadsheet recalculation, task schedulers, and any "can this be arranged" question where the constraints are pairwise and one sided.