水が流れていく方法の数

import sysfrom collections import deque MOD = 1_000_000_007data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) down = [[] for _ in range(n + 1)]  # down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)inflow = [0] * (n + 1)  # 아직 계산하지 않은, 들어오는 물길의 수for i in range(m):    a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])    down[a].append(b)    inflow[b] += 1 # 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 차례로 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = [0] * (n + 1)  # ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1ready = deque(v for v in range(1, n + 1) if inflow[v] == 0)while ready:    v = ready.popleft()    for nxt in down[v]:        ways[nxt] = (ways[nxt] + ways[v]) % MOD        inflow[nxt] -= 1        if inflow[nxt] == 0:            ready.append(nxt) # 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0for v in range(1, n + 1):    if not down[v]:        total = (total + ways[v]) % MODprint(total)

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const MOD = 1000000007; const down = Array.from({ length: n + 1 }, () => []); // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)const inflow = new Array(n + 1).fill(0); // 아직 계산하지 않은, 들어오는 물길의 수for (let i = 0; i < m; i++) {  const a = data[2 + 2 * i], b = data[3 + 2 * i];  down[a].push(b);  inflow[b]++;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)const ways = new Array(n + 1).fill(0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1;const queue = [];for (let v = 1; v <= n; v++) if (inflow[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) {  const v = queue[head];  for (const next of down[v]) {    ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다    if (--inflow[next] === 0) queue.push(next);  }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다let total = 0;for (let v = 1; v <= n; v++) if (down[v].length === 0) total = (total + ways[v]) % MOD;console.log(total);

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const MOD = 1000000007; const down: number[][] = Array.from({ length: n + 1 }, (): number[] => []); // down[a] = a에서 물이 흘러가는 칸들const inflow: number[] = new Array<number>(n + 1).fill(0); // 아직 계산하지 않은, 들어오는 물길의 수for (let i = 0; i < m; i++) {  const a = data[2 + 2 * i], b = data[3 + 2 * i];  down[a].push(b);  inflow[b]++;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)const ways: number[] = new Array<number>(n + 1).fill(0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1;const queue: number[] = [];for (let v = 1; v <= n; v++) if (inflow[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) {  const v = queue[head];  for (const next of down[v]) {    ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다    if (--inflow[next] === 0) queue.push(next);  }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다let total = 0;for (let v = 1; v <= n; v++) if (down[v].length === 0) total = (total + ways[v]) % MOD;console.log(total);

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer; public class Main {    static final int MOD = 1_000_000_007;     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(in.readLine());        int n = Integer.parseInt(st.nextToken());        int m = Integer.parseInt(st.nextToken());         List<List<Integer>> down = new ArrayList<>(); // down.get(a) = a에서 물이 흘러가는 칸들        for (int v = 0; v <= n; v++) down.add(new ArrayList<>());        int[] inflow = new int[n + 1]; // 아직 계산하지 않은, 들어오는 물길의 수        for (int i = 0; i < m; i++) {            st = new StringTokenizer(in.readLine());            int a = Integer.parseInt(st.nextToken());            int b = Integer.parseInt(st.nextToken());            down.get(a).add(b);            inflow[b]++;        }         // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)        long[] ways = new long[n + 1]; // 두 나머지의 합은 int를 넘을 수 있어 long        ways[1] = 1;        ArrayDeque<Integer> ready = new ArrayDeque<>();        for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.add(v);        while (!ready.isEmpty()) {            int v = ready.poll();            for (int next : down.get(v)) {                ways[next] = (ways[next] + ways[v]) % MOD;                if (--inflow[next] == 0) ready.add(next);            }        }        // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다        long total = 0;        for (int v = 1; v <= n; v++) if (down.get(v).isEmpty()) total = (total + ways[v]) % MOD;        System.out.println(total);    }}

using System;using System.Collections.Generic; class Program{    const long MOD = 1_000_000_007;     static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(first[0]);        int m = int.Parse(first[1]);         var down = new List<int>[n + 1]; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)        for (int v = 0; v <= n; v++) down[v] = new List<int>();        var inflow = new int[n + 1]; // 아직 계산하지 않은, 들어오는 물길의 수        for (int i = 0; i < m; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            int a = int.Parse(p[0]), b = int.Parse(p[1]);            down[a].Add(b);            inflow[b]++;        }         // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)        var ways = new long[n + 1]; // 두 나머지의 합은 int를 넘을 수 있어 long        ways[1] = 1;        var ready = new Queue<int>();        for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.Enqueue(v);        while (ready.Count > 0)        {            int v = ready.Dequeue();            foreach (int next in down[v])            {                ways[next] = (ways[next] + ways[v]) % MOD;                if (--inflow[next] == 0) ready.Enqueue(next);            }        }        // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다        long total = 0;        for (int v = 1; v <= n; v++) if (down[v].Count == 0) total = (total + ways[v]) % MOD;        Console.WriteLine(total);    }}

#include <iostream>#include <queue>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    const long long MOD = 1000000007;    int n, m;    std::cin >> n >> m;     std::vector<std::vector<int>> down(n + 1); // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)    std::vector<int> inflow(n + 1, 0);         // 아직 계산하지 않은, 들어오는 물길의 수    for (int i = 0; i < m; i++) {        int a, b;        std::cin >> a >> b;        down[a].push_back(b);        inflow[b]++;    }     // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)    std::vector<long long> ways(n + 1, 0); // 두 나머지의 합은 int를 넘을 수 있어 long long    ways[1] = 1;    std::queue<int> ready;    for (int v = 1; v <= n; v++)        if (inflow[v] == 0) ready.push(v);    while (!ready.empty()) {        int v = ready.front();        ready.pop();        for (int next : down[v]) {            ways[next] = (ways[next] + ways[v]) % MOD;            if (--inflow[next] == 0) ready.push(next);        }    }    // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다    long long total = 0;    for (int v = 1; v <= n; v++)        if (down[v].empty()) total = (total + ways[v]) % MOD;    std::cout << total << "\n";}

#include <stdio.h> #define MAXN 10001#define MAXM 10000#define MOD 1000000007LL /* 인접 목록을 배열로: head[a]는 a에서 나가는 첫 물길 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM];static int inflow[MAXN];  /* 아직 계산하지 않은, 들어오는 물길의 수 */static long long ways[MAXN]; /* 두 나머지의 합은 int를 넘을 수 있어 long long */static int queue[MAXN]; int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int v = 1; v <= n; v++) head[v] = -1;    for (int e = 0; e < m; e++) {        int a, b;        scanf("%d %d", &a, &b);        to[e] = b;        next[e] = head[a];        head[a] = e;        inflow[b]++;    }     /* 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다) */    ways[1] = 1;    int qh = 0, qt = 0;    for (int v = 1; v <= n; v++)        if (inflow[v] == 0) queue[qt++] = v;    while (qh < qt) {        int v = queue[qh++];        for (int e = head[v]; e != -1; e = next[e]) {            int b = to[e];            ways[b] = (ways[b] + ways[v]) % MOD;            if (--inflow[b] == 0) queue[qt++] = b;        }    }    /* 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다 */    long long total = 0;    for (int v = 1; v <= n; v++)        if (head[v] == -1) total = (total + ways[v]) % MOD;    printf("%lld\n", total);    return 0;}

MOD = 1000000007;첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 칸 번호에서 1을 빼 0번부터 둔다down = []; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)繰り返す (v = 0; v < n; v++){    down.追加([]);}inflow = 新リスト(n, 0); // 아직 계산하지 않은, 들어오는 물길의 수繰り返す (i = 0; i < m; i++){    물길 = コンソール.数読み();    down[물길[0] - 1].追加(물길[1] - 1);    inflow[물길[1] - 1] += 1;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = 新リスト(n, 0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[0] = 1;queue = [];繰り返す (v = 0; v < n; v++){    もし (inflow[v] == 0)    {        queue.追加(v);    }}繰り返す (head = 0; head < queue.個数; head++){    v = queue[head];    それぞれ (next の中 down[v])    {        ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다        inflow[next] -= 1;        もし (inflow[next] == 0)        {            queue.追加(next);        }    }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0;繰り返す (v = 0; v < n; v++){    もし (down[v].個数 == 0)    {        total = (total + ways[v]) % MOD;    }}コンソール.書く(total);