Compute build order from dependencies
Overview
This question evaluates understanding of graph algorithms and dependency resolution, specifically topological ordering and cycle detection, within the Coding & Algorithms domain and tests both conceptual understanding and practical application of graph traversal and ordering techniques.
Given a set of package build dependencies, output a valid build order so that each package is built only after all of its dependencies. The input is a list of (package, dependency) pairs or an adjacency list. Return one valid order, or report that no order exists if there is a cycle. Explain your algorithm, analyze time and space complexity, handle edge cases such as disconnected components and duplicate dependencies, and compare a BFS in-degree approach (Kahn's algorithm) with a DFS post-order approach, justifying your choice.