Longest Path in a DAG

HardPython

Problem

RAMP Consulting Group models dependency pipelines as a directed acyclic graph, where an edge u -> v means pipeline step u must complete before step v. Given the number of steps and dependency edges, return one longest pipeline as an ordered list of node IDs.

The path length is measured by the number of nodes. If multiple longest paths exist, return the lexicographically smallest path, meaning the path with the smallest differing node ID. Isolated nodes are valid paths of length one. The input is guaranteed to represent a DAG.

Formal Specification

Implement longest_pipeline_path(n, edges).

n is an integer representing nodes 0 through n - 1.
edges is a list of two-element lists [u, v], representing a directed edge from u to v.
Return a list of node IDs representing the selected longest path.
Return [] when n == 0.

Constraints

0 <= n <= 100000
0 <= len(edges) <= 200000
0 <= u, v < n
u != v
The graph is guaranteed to be acyclic
Duplicate edges are absent

Function Signature

def longest_pipeline_path(n, edges):

Formal Specification

Implement longest_pipeline_path(n, edges).

n is an integer representing nodes 0 through n - 1.
edges is a list of two-element lists [u, v], representing a directed edge from u to v.
Return a list of node IDs representing the selected longest path.
Return [] when n == 0.