Expecting One Correct Topological Order

Most directed acyclic graphs have more than one topological order, so a correct order cannot be checked by comparing it with one expected answer. This card runs Kahn's algorithm twice on the topic's graph, once with a queue of ready vertices and once with a stack, and checks both orders edge by edge.

The symptom is a test that fails on a correct program, or a reviewer who marks a correct order wrong. The trigger is treating the topological order as if it were a sorted list, which has exactly one answer. The table gives both runs.

The mechanism is the choice among ready vertices. At the start C and D are both ready, and nothing in the graph says which goes first. The queue takes C, the first to join; the stack takes D, the last. From then on the two runs make different choices whenever two vertices are ready together, and every such choice is allowed, because a ready vertex has no unmet dependencies. A run that tried all 720 orders of the six vertices found 12 that point every edge forwards.

The cost is wasted debugging, or a correct solution rejected by a judge that compares with one string. It is worst when the expected answer came from a different implementation, because a change as small as the order of the neighbour lists changes the output.

The remedy is to check the property, not the answer: every vertex appears exactly once, and for every edge u->v, u comes before v. That check is O(V + E) with a map from vertex to position. When one particular order is genuinely needed, such as the alphabetically smallest, say so and keep the ready vertices in a priority queue instead.