Game Routes

#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);
	cin.tie(0);
	int m;
	cin >> n >> m;
	int in_degree[n + 1], dp[n + 1];
	for (int i = 0; i <= n; i++) {
		in_degree[i] = 0;
		dp[i] = 0;
	}
	dp[1] = 1;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		backedge[b].push_back(a);
		in_degree[b]++;
	}
	// usa el algoritmo de Kahn
	queue<int> q;
	for (int i = 0; i < n; i++) {
		if (in_degree[i] == 0) { q.push(i); }
	}
 
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int next : edge[node]) {
			in_degree[next]--;
			if (in_degree[next] == 0) q.push(next);
		}
 
		for (int prev : backedge[node]) {
			dp[node] = (dp[node] + dp[prev]) % 1000000007;
		}
	}
	cout << dp[n] << endl;
	return 0;
}

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;
 
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
 
		forwards = new ArrayList[N];
		backwards = new ArrayList[N];
		degree = new int[N];
 
		for (int i = 0; i < N; i++) {
			forwards[i] = new ArrayList<>();
			backwards[i] = new ArrayList<>();
		}
 
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(r.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			forwards[a].add(b);
			backwards[b].add(a);
			degree[b]++;
		}
 
		// dp[i] es la cantidad de formas de llegar al nodo i.
		dp = new int[N];
		dp[0] = 1;
 
		// Agregar a la cola los nodos fuente que solo tienen aristas salientes.
		Queue<Integer> q = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			if (degree[i] == 0) { q.add(i); }
		}
 
		while (!q.isEmpty()) {
			// Sacar el nodo de la cola y revisar sus vecinos.
			int cur = q.poll();
			for (int next : forwards[cur]) {
				degree[next]--;
				// Agregar las nuevas fuentes a la cola.
				if (degree[next] == 0) { q.add(next); }
			}
 
			// Calcular la cantidad de formas revisando hacia atrás.
			for (int prev : backwards[cur]) { dp[cur] = (dp[cur] + dp[prev]) % MOD; }
		}
		System.out.println(dp[N - 1]);
	}
}

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)
dp = [0] * (n + 1)
 
dp[1] = 1
 
for _ in range(m):
	a, b = map(int, input().split())
	edge[a].append(b)
	backedge[b].append(a)
	in_degree[b] += 1
 
# usa el algoritmo de Kahn
q = deque()
 
for i in range(1, n + 1):
	if in_degree[i] == 0:
		q.append(i)
 
while q:
	node = q.popleft()
 
	for next_node in edge[node]:
		in_degree[next_node] -= 1
		if in_degree[next_node] == 0:
			q.append(next_node)
 
	for prev_node in backedge[node]:
		dp[node] = (dp[node] + dp[prev_node]) % MOD
 
print(dp[n])