一日一题（23）

链接：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))