AT_dp_g Longest Path
题目描述
给定一个有 $N$ 个顶点、$M$ 条边的有向图 $G$。顶点编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq M$），第 $i$ 条有向边从顶点 $x_i$ 指向顶点 $y_i$。$G$ 不包含有向环。
请你求出 $G$ 中所有有向路径中最长的那条路径的长度。这里，有向路径的长度指的是该路径上包含的边的数量。
输入格式
输入以如下格式从标准输入读入。
> $N$ $M$
> $x_1$ $y_1$
> $x_2$ $y_2$
> $\vdots$
> $x_M$ $y_M$
输出格式
输出 $G$ 中所有有向路径中最长的那条路径的长度。
说明/提示
## 限制条件
- 所有输入均为整数。
- $2 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $1 \leq x_i, y_i \leq N$
- 所有的 $(x_i, y_i)$ 均互不相同。
- $G$ 不包含有向环。
## 样例解释 1
下图中红色的有向路径是最长的。
## 样例解释 2
下图中红色的有向路径是最长的。
## 样例解释 3
例如，下图中红色的有向路径是最长的。
由 ChatGPT 4.1 翻译