# K3004-Editorial

Problem Code: K3004

Problem Name: help me!!

Difficulty: Medium

Prerequisites:
DP, Kahn’s Algorithm

Problem Statement:
Given a directed graph G, count all possible ways of reaching the vertex N from 1.
Note: There is no cycle in graph.

Explanation:
Let dp[i] denote the number of paths reaching ‘i’. dp[i] is the sum of all dp[j] where there exists an edge from j to i. We assign dp[Starting Node]=1, And visit the nodes in topological order. Use Kahn’s Algorithm to visit nodes in topological order.

Solution
``````#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int main()
{
ll n,m,a,b;
cin>>n>>m;
vector<ll> indegree(n,0),dp(n,0);
for(ll i=0;i<m;i++)
{
cin>>a>>b;
a--;
b--;
backedge[b].push_back(a);
indegree[b]++;
}
queue<ll> q;
for(ll i=0;i<n;i++)
if(indegree[i]==0)
q.push(i);
dp[0]=1;
while(!q.empty())
{
a=q.front();
q.pop();
{
}
for(ll i=0;i<backedge[a].size();i++)
dp[a]=(dp[a]+dp[backedge[a][i]])%mod;
}
cout<<dp[n-1];
return 0;
}
``````

Time Complexity:
O(n+m)

Feel free to share your approach, suggestions are welcome.

2 Likes

Thanks for the editorial.

1 Like