为了计算有向无环图（DAG）的最长路径，可以使用拓扑排序结合动态规划的方法。以下是详细的步骤

步骤 1：检查图是否为DAG

确定图是否为DAG，如果有环，则最长路径可能不存在或为无限,需特别处理。

步骤 2：拓扑排序

对图进行拓扑排序，得到一个节点的顺序，使得每个节点在所有其依赖节点之前处理，节点1→2和1→3的拓扑排序可能是1、2、3。

步骤 3：初始化最长路径长度

为每个节点初始化最长路径长度为。

步骤 4：计算最长路径

从最后一个节点开始，依次计算每个节点的最长路径长度,每个节点的最长路径长度为其所有出边节点最长路径长度的最大的值加1。

• 节点4的最长路径长度为。
• 节点3的最长路径长度为节点4的最长路径长度加1,即1。
• 节点2的最长路径长度为节点4的最长路径长度加1,即1。
• 节点1的最长路径长度为节点2和3的最长路径长度的最大值加1,即2。

步骤 5：结果

图中最长路径的长度即为最后一个节点的最长路径长度，在上述例子中，图最长路径为2（1→2→4或1→3→4）。

代码示例

import sys
from collections import deque
def main():
    n = int(sys.stdin.readline())
    adj = [[] for _ in range(n)]
    edges = []
    for _ in range(n-1):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        edges.append((u, v))
    # 检查是否有环
    in_degree = [] * n
    for u, v in edges:
        in_degree[v] += 1
    queue = deque()
    for u in range(n):
        if in_degree[u] == 0:
            queue.append(u)
    topo_order = []
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    # 如果拓扑排序后的节点数不等于n，说明有环
    if len(topo_order) != n:
        print("图中存在环，无法计算最长路径")
        return
    # 初始化最长路径
    max_len = [] * n
    # 从最后一个节点开始计算
    for u in reversed(topo_order):
        max_len[u] = 0
        for v in adj[u]:
            if max_len[v] > max_len[u]:
                max_len[u] = max_len[v] + 1
    print(max_len[topo_order[-1]])
if __name__ == '__main__':
    main()

输出结果

2

说明

• 输入：读取图的节点数和边,构建邻接表。
• 拓扑排序：使用 Kahn算法进行拓扑排序,确保图是DAG。
• 最长路径计算：从最后一个节点开始,按拓扑顺序计算每个节点的最长路径长度。
• 结果输出：输出图中最长路径的长度。

这个方法有效地结合了拓扑排序和动态规划,确保在处理DAG时能够高效地计算最长路径。