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$ 中所有有向路径中最长的那条路径的长度。

输入输出样例 #1

输入 #1

4 5
1 2
1 3
3 2
2 4
3 4

输出 #1

3

输入输出样例 #2

输入 #2

6 3
2 3
4 5
5 6

输出 #2

2

输入输出样例 #3

输入 #3

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

输出 #3

3

说明/提示

限制条件

• 所有输入均为整数。
• $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 翻译