Game Routes

    1#include <bits/stdc++.h>
    2using namespace std;
    3const int mod = 1e9 + 7;
    4//idea is to use toposort to ensure that u always before v for every direct edge u - v and then accumulate cnt of paths 
    5int main(){
    6    ios::sync_with_stdio(0);
    7    cin.tie(0);
    8    int n, m; cin >> n >> m;
    9    vector<vector<int>> adj(n + 1);
    10    vector<int> indegree(n + 1);
    11    for(int i = 0; i < m; i++){
    12        int a, b; cin >> a >> b;
    13        adj[a].push_back(b);
    14        indegree[b]++;
    15    }
    16    queue<int> q;
    17    vector<int> res;
    18    for(int i = 0; i < indegree.size(); i++){
    19        if(indegree[i] == 0) q.push(i);
    20    }
    21    while(!q.empty()){
    22        int node = q.front(); q.pop();
    23        res.push_back(node);
    24        for(int nxt : adj[node]){
    25            if(!--indegree[nxt]) q.push(nxt);
    26        }
    27    }
    28    vector<int> dp(n + 1); dp[1] = 1; // base case
    29    for(int i = 0; i < res.size(); i++){
    30        int cur = res[i];
    31        for(int nxt : adj[cur]){
    32            dp[nxt] += dp[cur];
    33            dp[nxt] %= mod;
    34        }
    35    }
    36    cout << dp[n] << '\n';
    37    return 0;
    38}