Chương trình tìm độ dài đường đi dài nhất trong DAG không lặp nút trong Python

Cho một đồ thị có hướng không chu trình (DAG) dưới dạng danh sách kề. Tìm độ dài đường đi dài nhất không lặp lại nút nào.

Ví dụ: đồ thị [[1,2], [3,4], [], [4], [2]] → đường đi dài nhất là 0→1→3→4→2 (độ dài 4 cạnh, 5 nút). Kết quả: 4.

Giải thuật (DFS + Memoization / DP trên DAG)

• Khởi tạo mảng table kích thước n (số nút) với giá trị -1 (chưa tính).
• Hàm dfs(u) trả về độ dài đường đi dài nhất bắt đầu từ nút u:
  • Nếu table[u] != -1, trả về giá trị đã lưu.
  • Khởi tạo p_len = 0.
  • Với mỗi nút kề v của u: p_len = max(p_len, 1 + dfs(v)).
  • Lưu table[u] = p_len và trả về.
• Gọi dfs(i) cho mọi nút i, lấy max làm kết quả.

Mã nguồn Python

class Solution:
    def solve(self, graph):
        ans = 0
        n = len(graph)
        table = [-1] * n
        def dfs(u):
            if table[u] != -1:
                return table[u]
            p_len = 0
            for v in graph[u]:
                p_len = max(p_len, 1 + dfs(v))
            table[u] = p_len
            return p_len
        for i in range(n):
            ans = max(ans, dfs(i))
        return ans

ob = Solution()
graph = [[1, 2], [3, 4], [], [4], [2]]
print(ob.solve(graph))  # Output: 4

Đầu vào

graph = [[1, 2],[3, 4],[],[4],[2]]

Đầu ra

4