{ }codelper
dynamic programminggraphs (adjacency lists)topological sortP0154

Ways the water can flow

There are n plots for watering rice fields, numbered 1 to n. Between the plots there are m canals. A canal "a b" means water flows only from plot a to plot b. There may be several canals between the same two plots; different canals count as different even if they join the same two plots. Water following the canals from any plot never comes back to that plot. When water is poured into plot 1 (the spring), it repeatedly picks one of the canals leaving its current plot and flows along it, and when it reaches a plot with no canal leaving it, it pools there and stops. Find how many different ways the water can flow. Two ways are different if the sequences of canals they pass through differ. If no canal leaves plot 1, the water pools in plot 1 as it is, and that also counts as one way. The number can be very large, so print it modulo 1,000,000,007.

Input
The first line has n and m; each of the next m lines has a and b separated by a space.
1 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 1 ≤ a, b ≤ n, a ≠ b.
There is no loop that comes back along the canals.
Output
The number of ways the water can flow, modulo 1,000,000,007
Example 1 · stdin
5 6
1 2
1 3
2 4
3 4
4 5
1 5
stdout
3
Example 2 · stdin
6 6
1 2
1 3
2 4
3 4
3 5
6 2
stdout
3
Example 3 · stdin
3 0
stdout
1
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

With ways[v] = 'the number of ways water can flow from plot 1 to v', add the ways of the start plot of every canal coming into v (dynamic programming).
The answer is the sum of ways over every plot with no canal leaving it (where water pools) — if no canal leaves plot 1, plot 1 is such a plot, and ways[1] = 1 is the answer as it is (the third example).
But the start plot's value must be finished before adding, so let the water flow in topological order, taking plots whose incoming canals are all done first (Kahn's algorithm — count inflow and queue a plot when it reaches 0).
Trap one: starting the queue with only plot 1 leaves canals from plots that plot 1 cannot reach (plot 6 in the second example) in inflow, so the plots below are never taken out — queue every plot with no incoming canal (their ways are 0, so the answer does not change).
Trap two: flowing in number order is wrong — nothing promises that smaller numbers are higher up.
Trap three: leaving plot 1, where the water is poured, out of the pooling plots gives 0 in the third example.
Trap four: the count grows like 2^2500.
Take the remainder after every addition: even C and C++ long long overflows if you divide only once at the end, and Python does not overflow but prints the huge number if you never divide.
The sum of two remainders is about 2 billion, which only just fits in a 32-bit int (about 2.1 billion), so to be safe keep it in C and C++ long long or Java and C# long; JavaScript, TypeScript and Craykon numbers are exact up to 2^53, so they work as they are.
Trap five: counting count(v) with memoized recursion goes past Python's default recursion limit (1,000) on a 10,000-plot chain (RecursionError), and Craykon stops at around 4,000 levels too — the queue-based topological sort has no depth.
Queues differ by language: Python collections.deque, Java ArrayDeque<Integer>, C# Queue<int>, C++ std::queue<int>, C an array with front and back positions, and JavaScript, TypeScript and Craykon only append to a list and move a front index (head) (shift() moves everything each time and is slow).
Craykon lists hold up to 10,000 items, so it subtracts 1 from each number to start at 0 (NewList(n, 0)).

Pythonmain.py · 32 lines
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)
JavaScriptmain.js · 28 lines
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);
TypeScriptmain.ts · 30 lines
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);
JavaMain.java · 46 lines
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);    }}
C#Main.cs · 44 lines
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);    }}
C++main.cpp · 40 lines
#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";}
Cmain.c · 45 lines
#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;}
Craykonmain.cray · 53 lines
MOD = 1000000007;첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 칸 번호에서 1을 빼 0번부터 둔다down = []; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)for (v = 0; v < n; v++){    down.Add([]);}inflow = NewList(n, 0); // 아직 계산하지 않은, 들어오는 물길의 수for (i = 0; i < m; i++){    물길 = Console.ReadNumbers();    down[물길[0] - 1].Add(물길[1] - 1);    inflow[물길[1] - 1] += 1;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = NewList(n, 0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[0] = 1;queue = [];for (v = 0; v < n; v++){    if (inflow[v] == 0)    {        queue.Add(v);    }}for (head = 0; head < queue.Count; head++){    v = queue[head];    foreach (next in down[v])    {        ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다        inflow[next] -= 1;        if (inflow[next] == 0)        {            queue.Add(next);        }    }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0;for (v = 0; v < n; v++){    if (down[v].Count == 0)    {        total = (total + ways[v]) % MOD;    }}Console.WriteLine(total);