Graphs
Dependencies, cycles, and a valid order
Two questions with one algorithm: is there a cycle, and if not, what order satisfies everything.
Key idea
Prerequisites are a directed graph
A rule that one thing must come before another is a directed edge. A set of such rules is a directed graph, and the question of whether they can all be satisfied is the question of whether that graph has a cycle.
If it does, the requirements are contradictory and no order exists. If it does not, at least one valid order exists and the algorithm that detects the cycle also produces one.
Why it works
Repeatedly take whatever has nothing left blocking it
Count, for each node, how many things must come before it. Start with everything whose count is zero, since those are unblocked. Take one, output it, and reduce the count of everything that depended on it. Anything whose count reaches zero is now unblocked.
The invariant: the queue always holds exactly the nodes with no unsatisfied prerequisites. When the process ends, either everything was output, or the remainder is stuck in a cycle.
That final comparison is the cycle detection. Count what came out; if it is fewer than the number of nodes, the rest form a cycle.
Below, the counts are built and then a single node is taken out, so that the releasing step is visible on its own.
Gotcha
Which way does the edge point?
Problems state this in both directions. Take this course, but only after that one gives a pair where the second element must come first. Read carefully and write down which element of the pair is the prerequisite before building anything.
Getting it backward produces a valid order for the reversed problem, which passes symmetric test cases and fails the rest. If a topological solution is right on some inputs and wrong on others, check the edge direction first.
Tip
There is usually more than one right answer
In the example, 1 and 2 could come in either order. Both are valid. Problems of this kind normally accept any valid order, which is worth confirming, because a grader comparing against one fixed answer would be checking something else.
The order produced depends on how the unblocked set is stored. A queue gives one order, a stack another, and a heap gives the smallest available at each step, which is what a problem asking for the lexicographically smallest order wants.
Key idea
The depth-first alternative
The other standard approach recurses, marking each node as in progress on the way down and finished on the way back up. Meeting a node that is in progress means an edge back into the current path, which is a cycle.
The finish order, reversed, is a valid topological order. It is elegant and slightly harder to get right, because there are three states rather than two and confusing not-yet-seen with finished silently breaks the cycle detection.
Either is a good answer. The counting version is easier to explain out loud and gives the cycle answer as a comparison of two numbers rather than as a state machine.
Cost
Cost
Every node is queued once and every edge is examined once, so O(nodes plus edges) time and the same space for the adjacency map and counts.
That is the standard complexity for graph algorithms and the form to quote. Saying O(n) is ambiguous when there are two sizes in play.
Find the reversed edge
This is meant to count, for each node, how many things must come before it. On the pairs [(0, 1), (0, 2)] it reports [2, 0, 0] when it should report [0, 1, 1]. Click the line that is wrong.
This activity type is not wired up yet.
Course Schedule
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Course Schedule Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.