Topological Ordering for Dependencies

An AMD ROCm build pipeline contains tasks such as kernel compilation, linking, testing, and packaging. Each dependency is given as [prerequisite, task], meaning the prerequisite must be completed before the task.

Implement dependency_order(tasks, dependencies) to return the lexicographically smallest valid completion order. If the dependency graph contains a cycle, return an empty list because no valid order exists. Tasks with no dependencies must still appear in the result. Duplicate dependency pairs should be treated as one dependency.

Formal Specification

• Input tasks: a list of unique strings representing all tasks.
• Input dependencies: a list of two-element lists [prerequisite, task].
• Output: a list containing every task exactly once in valid dependency order, or [] if a cycle exists.
• The lexicographically smallest order is required when multiple valid orders exist.