Game Routes

A game has n levels, connected by m teleporters, and your task is to get from level 1 to level n. The game has been designed so that there are no directed cycles in the underlying graph. In how many ways can you complete the game?

Example:

Input: n = 4, m = 5, edges = {{1, 2}, {2, 4}, {1, 3}, {3, 4}, {1, 4}}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
bool vis[100005];
vector<int> v;
const int md = 1000000007;

//dfs function
void dfs(int s)
{
    //if alredy visted
    if (vis[s])
        return;

    //mark as visited
    vis[s] = 1;

    //call for all the adjacency list of the current
    //node
    for (auto i : adj[s])
        dfs(i);
    v.push_back(s);
}
int gameRoutes(int n, int m,
               vector<vector<int>> &edges)
{

    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
            dfs(i);
    }

    vector<int> t;
    int i = 0, f = 0;
    while (i < v.size())
    {
        if (f == 0)
        {
            if (v[i] == 1)
            {
                f = 1;
                t.push_back(1);
            }
        }
        else
        {
            t.push_back(v[i]);
        }
        i++;
    }
    int path[100005] = {0};
    path[1] = 1;
    for (auto i : t)
    {
        for (auto j : adj[i])
        {
            (path[i] += path[j]) %= md;
        }
    }
    return path[n];
}
int main()
{

    int n = 4, m = 5;

    vector<vector<int>> edges = {{1, 2},
                                 {2, 4},
                                 {1, 3},
                                 {3, 4},
                                 {1, 4}};

      cout << gameRoutes(n, m, edges) << "\n";

    return 0;
}