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

🔗 🟡 AT_dp_g Longest Path

Problem Statement

題目簡述

給定一個 $N$ 個頂點、 $M$ 條邊的有向無環圖 (DAG)，求圖中最長有向路徑的長度（即路徑所包含的邊數）。

Constraints

約束條件

$2 \le N \le 10^5$
$1 \le M \le 10^5$
圖不含有向環

思路：拓撲排序 + DP

本題是經典的 DAG 最長路徑問題。由於圖中不含有向環，我們可以利用拓撲排序 (Topological Sort) 的順序來進行動態規劃，確保在計算某個節點的狀態時，其所有前驅節點的狀態都已經計算完畢。

狀態定義

定義 $f[u]$ 為以節點 $u$ 為終點的最長路徑長度。

替代定義與記憶化搜索

也可以定義 $f[u]$ 為以節點 $u$ 為起點的最長路徑長度，這等價於在反圖上定義 $u$ 為終點。
對於拓樸序DP的問題，也可以使用 記憶化搜索 (DFS + Memoization) 來實現，然而需要注意遞迴時與迭代的順序是相反的。

轉移方程

對於圖中的每一條有向邊 $u \to v$ ：

f[v] = \max(f[v], f[u] + 1)

初始化：所有節點的 $f[u]$ 初始值為 $0$ 。
計算順序：依照拓撲序（入度為 0 的節點優先）進行更新。
最終答案： $\max_{u} \{ f[u] \}$ 。

為什麼需要拓撲排序？

在 BFS 過程中，僅當節點 $v$ 的入度減為 0 時（意味著 $v$ 的所有前驅 $u$ 都已處理並更新過 $f$ 值），我們才將 $v$ 加入佇列。這保證了 DP 的無後效性。

複雜度分析

時間複雜度： $\mathcal{O}(N + M)$
完整的拓撲排序過程中，每個頂點進出佇列一次，每條邊被遍歷一次。
空間複雜度： $\mathcal{O}(N + M)$
主要空間消耗在於鄰接表 (g)、入度陣列 (deg) 以及 DP 陣列 (f)。

Code

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

    # f[u] 表示以 u 為終點的最長路徑長度
    f = [0] * n
    q = deque(u for u in range(n) if deg[u] == 0)
    while q:
        u = q.popleft()
        for v in g[u]:
            f[v] = max(f[v], f[u] + 1)
            deg[v] -= 1
            # 要確定 v 的所有前驅都已經被處理過了
            if deg[v] == 0:
                q.append(v)
    print(max(f))

if __name__ == "__main__":
    solve()