CSES - Game Routes

Authors: Andrew Wang, Sofia Yang

Appears In

Gold - Topological Sort

Solution

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,

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

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

Implementation

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

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n;
vector<int> edge[100001];
vector<int> backedge[100001];

int main() {

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;

Python

from collections import deque

MOD = 10**9 + 7

n, m = map(int, input().split())

edge = [[] for _ in range(n + 1)]
backedge = [[] for _ in range(n + 1)]

in_degree = [0] * (n + 1)

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!