Raythroughspace's blog

By Raythroughspace, history, 5 years ago, In English

So I tried submitting my solution for CSES game routes problem in graph algorithms and I get a runtime error for the very last test. I downloaded the test input and ran it on my compiler (CLion) and it output the correct answer? What is the problem with my code?

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main(){
    int n,m; cin>> n >> m;
    vector<vector<int>> adj(n+1);
    for (int i=0;i<m;i++){
        int a,b; cin>> a>>b;
        adj[a].push_back(b);
    }
    vector<int> sorted;
    vector<bool> visited(n+1);
    function<void(int)> topoS = [&] (int v){
        if (visited[v]) return;
        visited[v] = true;
        for (auto e: adj[v]){
            topoS(e);
        }
        sorted.push_back(v);
    };
    topoS(1);
    vector<int> paths(n+1); paths[1] = 1;
    reverse(sorted.begin(),sorted.end());
    for(int i=0;i<n;i++){
        for (auto e: adj[sorted[i]]){
            paths[e] += (paths[sorted[i]] % mod);
            paths[e] %= mod;
        }
    }
    cout << paths[n];
 
}
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Since there can be isolated nodes, they are not getting pushed in the sorted vector. And as in your bottom-up dp you are iterating upto n it gives the runtime error.

changing the n to sorted.size() will work.