LS 22 Longest path on DAG的最短路SPFA算法如何改写为长尾词？

本文共计497个文字，预计阅读时间需要2分钟。

输入：n个顶点，m条边，表示顶点数和边数。接下来的m行包含两个整数ai, bi，表示边ai→bi。（1≤n≤105，1≤m≤106，1≤ai, bi≤n）

输出：l，表示最长路径的长度。l=1+Sample

Longest path on DAG

G.

Input

n,m, which denote the number of vertices and edges.

mlines contains two integerai,bi, which denote edgeai→bi.

(1≤n≤105,1≤m≤106,1≤ai<bi≤n)

Ouptut

l, which denotes the length of longest path.

l+1

Sample input

4 41 21 32 43 4

Sample output

21 2 4

思路：建边，建个源点0和汇点，然后依次在源点和汇点与中间所有点连边。求源点和汇点的最长路就是答案。