#AT7. Longest Path
Longest Path
[G] Longest Path(dp_g)
来源: AtCoder Educational DP Contest - Problem G 原题时限:2 秒 / 内存:1024 MB
题目描述
有 个顶点(编号 )和 条有向边的有向图。第 条边从顶点 指向顶点 。
保证该图不含有向环。
求图中最长有向路径的长度(即路径上的边数)。
输入格式
输入由标准输入按以下格式给出:
N M
x_1 y_1
x_2 y_2
:
x_M y_M
输出格式
输出图中最长有向路径的长度。
数据范围
- 输入中的所有值均为整数。
- 所有有序对 互不相同。
- 图 中不含有向环。
样例 1
输入:
4 5
1 2
1 3
3 2
2 4
3 4
输出:
3
样例 2
输入:
6 3
2 3
4 5
5 6
输出:
2
样例 3
输入:
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
输出:
3