链接：https://atcoder.jp/contests/dp/tasks/dp_g
图片.png
题意为求一个有向图无环图上的最长路径。
有向无环图（DAG）是一个重要概念。往往很多模型都可以当做一个DAG。比如学生学习课程，学习一门课程需要修若干前置课程，那么可以将前置课程和本课程连有向边；又比如工厂生产零件，一道工序必须在另一道工序前面，或者只有做完某些工序，才能进行本工序，那么同样可以按照逻辑关系连有向边。
考虑本题，我们可以采用暴力搜索方式，求出每个点出发的所有路径。但是这是指数级别复杂度的。又想到动态规划，用表示到第
个点的最长路径。那么状态转移方程就是
这里表示直接连向
的所有节点——到达
，当然必须先经过
之一。
但是还有一个重要的事情要考虑：更新顺序。这是因为，如果在都没有被确定的情况下，
是不能被计算的。我们必须在确定
之前，确定好
。
注意，这里的顺序，实际上也就是之前所说学生修课的顺序、工厂生产的顺序。通过拓扑排序算法，我们可以确定出这样的顺序——图中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
拓扑排序思路很简单：
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
这里主要是维护每个点的入度，并且利用队列储存入度只为0的节点，只需要初次扫描表将入度为0的放入栈(队列)中。每一次删除边，将对应点的入度-1即可。
详细算法解析参考其他资料
from queue import Queue
n, m = map(int, input().split())
E = [[] for i in range(n + 1)]
ind = [0] * (n + 1)
dp = [0] * (n + 1)
Q = Queue()
for i in range(m):
x, y = map(int, input().split())
E[x].append(y)
ind[y] += 1
for i in range(1, n + 1):
if not ind[i]:
Q.put(i)
while not Q.empty():
u = Q.get()
for i in E[u]:
ind[i] -= 1
dp[i] = max(dp[i], dp[u] + 1)
if not ind[i]:
Q.put(i)
print(max(dp))
