CSES - Game Routes

Authors: Andrew Wang, Sofia Yang


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

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

dp[v]=edge uv existsdp[u],dp[v]= \sum_{\text{edge } u\to v \text{ exists}}dp[u],

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

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n;
vector<int> edge[100001];
vector<int> backedge[100001];
int main() {
ios_base::sync_with_stdio(0);

Java

import java.io.*;
import java.util.*;
public class cses1681 {
public static final int MOD = (int)1e9 + 7;
public static ArrayList<Integer>[] forwards;
public static ArrayList<Integer>[] backwards;
public static int[] degree;
public static int[] dp;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!