Count paths in a DAG

Challenge

long long count_paths_dag(const int *adj,int n,int src,int dst);

Return the number of distinct directed paths from src to dst in a DAG.

Input format

adj n×n DAG.

Output format

Path count (may be large → long long).

Constraints

Graph is acyclic.

Starter code

#include <stddef.h>
/* Number of distinct directed paths from src to dst in a DAG (adjacency matrix). */
long long count_paths_dag(const int *adj,int n,int src,int dst){ (void)adj;(void)n;(void)src;(void)dst; return 0; }

Common mistakes

Exponential recomputation without memoization; using int (overflow).

Edge cases to handle

src==dst → 1; no route → 0.

Background lessons

• Counting paths & reachability