Giả sử chúng ta có một đồ thị xoay chiều có hướng được biểu diễn bằng danh sách kề. Chúng ta phải tìm đường đi dài nhất trong biểu đồ mà không có nút lặp lại.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 4, vì đường dẫn là 0 -> 1 -> 3 -> 4 -> 2 với độ dài 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=0
- n:=số nút của biểu đồ
- table:=một danh sách có kích thước n và điền vào -1
- Định nghĩa một hàm dfs (). Điều này sẽ khiến bạn mất
- nếu bảng [u] không phải là -1, thì
- trả về bảng [u]
- p_len:=0
- đối với mỗi vectex v trong biểu đồ [u], hãy thực hiện
- p_len:=tối đa là p_len và (1 + dfs (v))
- bảng [u]:=p_len
- trả lại p_len
- Từ phương thức chính, hãy làm như sau -
- đối với tôi trong phạm vi từ 0 đến n, thực hiện
- ans:=tối đa ans, dfs (i)
- trả lại ans
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
graph = [[1, 2],[3, 4],[],[4],[2]]
Đầu ra
4