Longest path in a DAG

Challenge

int longest_path_dag(const int *adj,int n);

Return the number of edges on the longest directed path in a DAG (0 if there are no edges).

Input format

adj n×n DAG.

Output format

Longest path length in edges.

Constraints

Graph is acyclic.

Starter code

#include <stddef.h>
/* Length (in edges) of the longest path in a DAG (directed acyclic graph, adjacency matrix). */
int longest_path_dag(const int *adj,int n){ (void)adj;(void)n; return 0; }

Common mistakes

Recomputing subpaths (exponential) instead of memoizing.

Edge cases to handle

No edges → 0; a simple chain of k edges → k.

Background lessons

• In-degree & DAG ordering