Given a directed acyclic graph (a DAG — edges point one way, and there are no cycles, so you can never return to a node you've left), return the number of edges in the longest path anywhere in the graph. The "no cycles" property is what lets the recursion below terminate: a path can't loop forever.
longestPath(graph)
Input format: directed edges as a,b pairs (meaning a → b).
a,b b,c c,d // → 3 (a→b→c→d)
a,b a,c // → 1
(no edges) // → 0
The grid problems had built-in direction — only right or down — guaranteeing progress toward a fixed destination. A DAG generalizes that: edges point one way, and no cycles mean you can never loop back to a node you've visited. That's what guarantees the recursion terminates.
"The longest path starting at this node": if it has no outgoing edges, that's 0. Otherwise, for each neighbor, the path through it is 1 plus the longest path starting there. The longest path from the current node is the best across all neighbors.
Since the question asks for the longest path anywhere, the final answer is the max of "longest path starting here" over every node.
The same node can be reached from multiple starting points via different routes — a node with two incoming edges from two different earlier nodes. A naive implementation recomputes "longest path from this node" fresh every time another node's exploration reaches it, even though it only depends on the node itself and its outgoing edges.
The longest path from a node is a fixed property of that node and its outgoing edges — independent of who's asking. Cache from node to longest-path-from-here. Check before recursing; otherwise compute 1 + longest path for each neighbor, take the max (0 if none), cache, return.
Every node's value is computed once, at cost proportional to its outgoing edges — O(V + E) total instead of recomputing shared downstream nodes repeatedly. The acyclic property is what makes this safe: following edges can never lead back to a node still being computed.
def longest_path(graph):
memo = {}
def longest_from(node):
if node in memo:
return memo[node]
best = 0
for nxt in graph.get(node, []):
d = 1 + longest_from(nxt)
if d > best:
best = d
memo[node] = best
return best
overall = 0
for node in graph:
d = longest_from(node)
if d > overall:
overall = d
return overall
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.