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]$.

1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5int n;
6vector<int> edge[100001];
7vector<int> backedge[100001];
8
9int main(){
10    ios_base::sync_with_stdio(0); cin.tie(0);