題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P4017 最大食物链计数

Problem Statement

題目簡述

給定一個食物網（有向無環圖），求出其中「最大食物鏈」的數量。
一條「最大食物鏈」定義為：從一個沒有被其他生物捕食的生物（入度為 00 的節點）開始，一直到一個不捕食其他生物的生物（出度為 00 的節點）結束的路徑。
答案對 8011200280112002 取模。

Constraints

約束條件

  • 1≤n≤5⋅1031 \le n \le 5 \cdot 10^3
  • 1≤m≤5⋅1051 \le m \le 5 \cdot 10^5

思路：拓樸排序與記憶化搜索

這道題目本質上是在一個有向無環圖（DAG）中，尋找從「起點」（入度為 0 的節點）到「終點」（出度為 0 的節點）的路徑總數。
由於圖中沒有環，我們可以使用動態規劃的思想來解決。對於圖中的任意一個節點，到達該節點的路徑數，等於所有能直接走到該節點的前驅節點的路徑數之和。

根據計算順序的不同，我們可以採用兩種常見的實作方式：正向的拓樸排序，或是反向的記憶化搜索。

方法一：拓樸排序 DP

核心概念

按照拓樸序遍歷節點，確保在計算某個節點時，所有能到達它的前驅節點都已經計算完畢。

我們可以定義一個狀態陣列，用來記錄「從任意起點出發，到達目前節點的路徑總數」。
初始時，將所有起點（入度為 00 的節點）的狀態值設為 11，其餘節點設為 00。

接著，我們使用一個佇列來進行拓樸排序：

  1. 將所有入度為 0 的節點加入佇列。
  2. 每次從佇列中取出一個節點，並遍歷它能直接到達的相鄰節點。
  3. 將目前節點的狀態值累加到相鄰節點的狀態值上（記得取模）。
  4. 將相鄰節點的入度 −1-1。如果相鄰節點的入度變為 00，代表它的所有前驅節點都已處理完畢，將其加入佇列。

當拓樸排序結束後，我們只需要將所有終點（出度為 00 的節點）的狀態值加總，即為最終答案。

複雜度分析

  • 時間複雜度：O(n+m)\mathcal{O}(n + m)，其中 nn 為節點數，mm 為邊數。拓樸排序需要遍歷所有的節點和邊。
  • 空間複雜度：O(n+m)\mathcal{O}(n + m)，用於儲存圖的鄰接表、入度/出度陣列、狀態陣列以及拓樸排序的佇列。

方法二：記憶化搜索

核心概念

從起點出發，遞迴地向下尋找終點。為了避免重複計算相同的子問題，將已經計算過的節點結果儲存起來。

我們可以定義一個遞迴函數，其回傳值代表「從目前節點出發，到達任意終點的路徑總數」。
遞迴的終止條件是：如果目前節點是終點（出度為 0），則只有 1 條路徑（即停留在原地），回傳 1。

對於非終點的節點，我們遍歷它能直接到達的所有相鄰節點，將遞迴呼叫相鄰節點的回傳值累加起來，就是目前節點的答案。
為了避免重複計算，我們可以使用記憶化技術（例如 Python 的 @cache 裝飾器），將每個節點的計算結果快取起來。

最後，我們遍歷所有的起點（入度為 0 的節點），將它們的遞迴結果加總，即為最終答案。

複雜度分析

  • 時間複雜度：O(n+m)\mathcal{O}(n + m)。由於記憶化的存在，每個節點和每條邊最多只會被訪問一次。
  • 空間複雜度：O(n+m)\mathcal{O}(n + m)。用於儲存圖的鄰接表、入度/出度陣列，以及遞迴呼叫的系統堆疊空間（最壞情況下深度為 nn）。

Code

方法一：拓樸排序 DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from collections import deque

MOD = 80112002


def solve():
    n, m = map(int, input().split())

    g = [[] for _ in range(n)]
    ideg = [0] * n
    odeg = [0] * n
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        odeg[u] += 1
        ideg[v] += 1

    # f[u] 表示從一個入度為0的點出發，到達u的路徑數
    f = [0] * n
    q = deque()
    for u in range(n):
        if ideg[u] == 0:
            f[u] = 1
            q.append(u)

    while q:
        u = q.popleft()
        for v in g[u]:
            ideg[v] -= 1
            f[v] = (f[v] + f[u]) % MOD
            if ideg[v] == 0:
                q.append(v)

    ans = 0
    for u in range(n):
        if odeg[u] == 0:
            ans = (ans + f[u]) % MOD
    print(ans)


if __name__ == "__main__":
    solve()

方法二：記憶化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from functools import cache

MOD = 80112002


def solve():
    n, m = map(int, input().split())

    g = [[] for _ in range(n)]
    ideg = [0] * n
    odeg = [0] * n
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        odeg[u] += 1
        ideg[v] += 1

    # dfs(u) 表示從u出發，到達一個出度為0的點的路徑數
    @cache
    def dfs(u: int) -> int:
        if odeg[u] == 0:
            return 1
        res = 0
        for v in g[u]:
            res += dfs(v)
        return res

    ans = 0
    for u in range(n):
        if ideg[u] == 0:
            ans = (ans + dfs(u)) % MOD
    print(ans)


if __name__ == "__main__":
    solve()