CSES - Game Routes

Time Complexity: $\mathcal{O}(N+M)$

This problem is very similar to the "Longest Flight Route" problem discussed earlier in this module. Let $dp[v]$ denote the number of paths reaching $v$. We can see,

with an exception of $dp[1]$, or the starting node, having a value of 1. We process the nodes topologically so $dp[u]$ will already have been computed before $dp[v]$.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<int> edge[100001];
vector<int> backedge[100001];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);