← Back to problems
UNSW COMP2521 · medium

Topological Order (lexicographically smallest)

Topological Order (lexicographically smallest)

Given a directed graph (edge u v = u before v), print the lexicographically smallest topological order, or CYCLE if the graph has a cycle.

Input: line 1 V E; then E lines u v. Output: the lex-smallest topo order (space-separated), or CYCLE.

Use Kahn's algorithm with a min-heap of in-degree-0 nodes. Fewer than V popped ⇒ cycle.