Tutorial — Hành Trình Mạng

Nếu đồ thị chứa một chu trình có thể truy cập được, số lần xuất hiện của ký tự trên chu trình có thể tăng lên vô hạn, dẫn đến đáp án bằng -1.

Trên đồ thị có hướng không chu trình (DAG), ta có thể xác định thứ tự xử lý các đỉnh sao cho khi xét đến một đỉnh, tất cả các đường đi dẫn đến nó đều đã được tính toán xong.

Sử dụng thuật toán Kahn để sắp xếp topô các đỉnh và duy trì mảng quy hoạch động $dp[u][c]$ lưu số lần xuất hiện nhiều nhất của ký tự $c$ trên đường đi kết thúc tại $u$.