Determine Maximum Path Length in Directed Acyclic Graph

Scenario

A backend service represents task dependencies as a directed graph; you need to understand how deep the longest dependency chain can get.

Question

Given an adjacency list of a directed acyclic graph (DAG), implement a Python function max_depth(graph_dict) that returns the maximum number of nodes in any path.

Hints

Use DFS with memoization or topological ordering to avoid recomputation and cycles.

Maximum Nodes in a DAG Path

Given a directed acyclic graph (DAG) represented as a dictionary mapping each node (string) to a list of its outgoing neighbors (strings), return the maximum number of nodes in any directed path. If the graph has no nodes, return 0. Nodes that appear only in neighbor lists but not as keys should be treated as nodes with no outgoing edges. Count includes both start and end nodes of the path.

Constraints

• 0 <= number of nodes n <= 100000
• 0 <= number of edges m <= 200000
• Graph is directed and acyclic (DAG); no self-loops or parallel edges needed
• Node labels are unique non-empty strings
• Nodes may appear only in neighbor lists; treat them as having empty adjacency lists
• Return 0 for an empty graph
• Aim for O(n + m) time and O(n + m) space

Examples

Example 1

Input: graph_dict = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
Output: 3

Explanation: Longest paths A->B->D or A->C->D have 3 nodes.

Example 2

Input: graph_dict = {"A": ["B"], "C": []}
Output: 2

Explanation: Node B appears only as a neighbor and is a sink; longest path is A->B with 2 nodes.

Hints

1. Use either DFS with memoization or a topological ordering to avoid recomputation.
2. In topological order, let dp[u] be the longest path (in nodes) ending at u; relax edges u->v with dp[v] = max(dp[v], dp[u] + 1).
3. Be sure to include nodes that only appear in neighbor lists and treat missing keys as empty adjacency lists.

Approach

Compute a topological order using Kahn's algorithm while maintaining dp[u] as the maximum number of nodes in any path that ends at u. Initialize dp[u] = 1 for every node (path of just that node). For each edge u->v processed in topological order, update dp[v] = max(dp[v], dp[u] + 1). The answer is max(dp.values()) over all nodes. This approach naturally handles disconnected DAGs and nodes that appear only as neighbors by initializing them with empty adjacency lists.

• Time complexity: O(n + m)
• Space complexity: O(n + m)