Advanced Graphs
Deriving the graph from the input
The hardest part is not the algorithm. It is working out what the nodes and edges are.
Key idea
The graph is not given
In every problem so far the edges arrived in the input. Some problems instead describe a situation from which the constraints have to be extracted, and once they are, a standard algorithm finishes the job in a few lines.
For those, the work is entirely in the derivation. Writing down what a node is and what an edge means, in words, before any code, is the difference between a short solution and an hour of confusion.
Why it works
Adjacent items give one constraint each
When an ordering must be inferred from a sorted list of items, each adjacent pair yields exactly one piece of information: the position of their first difference tells you which symbol comes before which.
Only the first difference matters. Everything after it is unconstrained, because the earlier position already decided the order. Comparing every pair rather than adjacent ones, or reading past the first difference, both invent constraints that are not there.
Edge cases
The invalid case that has no first difference
If one word is a prefix of the next and is longer, such as abc followed by ab, no ordering can produce that. A longer word cannot precede its own prefix.
The loop above walks off the end without appending anything, silently accepting an impossible input. Detecting it needs an explicit check: if no difference was found and the first word is longer, report failure.
This is the single most commonly missed case in this problem, and it is the kind of thing that only appears in the hidden tests.
Key idea
After the derivation, it is a solved problem
Once the constraints are pairs of the form this before that, the rest is the topological ordering from Unit 12, including its cycle detection. Contradictory constraints show up as a cycle and mean no valid order exists.
Remember to include symbols that appear in the input but in no constraint. They can go anywhere, and leaving them out of the node set silently drops them from the answer, which is the isolated-node trap from U12.
Write these down first
What is a node? What does an edge mean, and which direction does it point? Which inputs produce edges, and which produce nothing? What input is impossible, and how would I detect it?
Four sentences. For the problem below they take five minutes and turn it from a hard problem into a derivation followed by an algorithm you have already written.
Find the invented constraint
This extracts ordering constraints from adjacent words. It produces constraints that the input does not actually imply. Click the line that is wrong.
This activity type is not wired up yet.
Cost of the derivation
Extracting constraints from n words of average length L, then topologically ordering the resulting graph over an alphabet of size a. Give the total time and the space for the graph.
Time
Space
Alien Dictionary
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.