Problem 37: Count Paths in DAG
Problem Statement: Given a directed acyclic graph (DAG) with n nodes and m edges, compute the number of distinct paths from node 1 to node n modulo 10^9+7.
Input
The first line contains two integers n and m. Each of the next m lines contains two integers u and v denoting an edge from u to v.
Output
Print the number of distinct paths from 1 to n modulo 10^9+7.
Examples
Input:
4 5
1 2
1 3
2 3
2 4
3 4
Output:
3
Solution Explanation
Method 1: Use dynamic programming and topological sorting to compute the number of paths from 1 to each node. Method 2: Use recursion with memoization on the DAG to count paths, ensuring each subproblem is solved only once.
Solution in C++
#include
#include
#include
using namespace std;
const int MOD = 1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector> adj(n+1);
vector indegree(n+1, 0);
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
indegree[v]++;
}
vector dp(n+1, 0);
dp[1] = 1;
queue q;
for(int i = 1; i <= n; i++){
if(indegree[i] == 0) q.push(i);
}
while(!q.empty()){
int u = q.front(); q.pop();
for(int v : adj[u]){
dp[v] = (dp[v] + dp[u]) % MOD;
indegree[v]--;
if(indegree[v] == 0) q.push(v);
}
}
cout << dp[n] << "
";
return 0;
}