K3004-Editorial

editorial
1

Problem Code: K3004

Problem Name: help me!!

Problem link: contest

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);
    vector<vector<ll>> adj(n),backedge(n);
    for(ll i=0;i<m;i++)
    {
         cin>>a>>b;
         a--;
         b--;
         adj[a].push_back(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<adj[a].size();i++)
        {
             indegree[adj[a][i]]--;
             if(indegree[adj[a][i]]==0)
                   q.push(adj[a][i]);
        }
        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
2

Thanks for the editorial.

1 Like