Problem Info
cses -game routes
link:CSES - Game Routes
My Work
#include<bits/stdc++.h>
using namespace std;
#define SPEED() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define MOD 1000000007
vector topo;
vector vis (1e5+1);
void dfs(ll x,vector<vector> adj){
if(vis[x]){
return;
}
vis[x]=1;
for(auto ele:adj[x]){
dfs(ele,adj);
}
topo.push_back(x);
}
int main(){
ll n,m;cin>>n>>m;
vector<vector> adj (n+1);
vector<vector> rev (n+1);
ll a,b,ans=0;
for(int i=0;i<m;i++){
cin>>a>>b;
adj[a].push_back(b);
rev[b].push_back(a);
}
vector<ll> dp (n+1);
dp[1]=1;
dfs(1,adj);
// for(auto ele:topo)
// cout<<ele<<" ";
reverse(topo.begin(),topo.end());
// for(auto ele: topo)
// cout<<ele<<" ";
for(auto ele:topo){
if (ele>1)
{
for(auto elee:rev[ele]){
dp[ele]+=dp[elee];
dp[ele]%=MOD;
}
}
}
cout<<dp[n]<<endl;
// for(int i=1;i<=n;i++){
// cout<<dp[i]<<endl;
// }
}
getting runtime error for large inputs