Tutorial — Mạng Lưới

Mạng lưới bài toán cho là một đồ thị không chứa chu trình có hướng, nghĩa là các liên kết chỉ đi theo một chiều nhất định và không bao giờ tạo thành lặp.

Do đồ thị không có chu trình, ta luôn có thể sắp xếp các nút theo thứ tự topo sao cho mọi liên kết đều đi từ nút đứng trước đến nút đứng sau.

Sử dụng thuật toán Kahn để duyệt đồ thị theo thứ tự topo và áp dụng quy hoạch động với $dp[u]$ là độ dài đường đi dài nhất kết thúc tại nút $u$, cập nhật $dp[v] = \max(dp[v], dp[u] + 1)$ với mỗi liên kết từ $u$ đến $v$.