Chương trình tìm giá trị màu lớn nhất trong đồ thị có hướng Python

Giả sử có một đồ thị có hướng với n nút có màu và m cạnh. Các nút được đánh số từ 0 đến n-1. Ta có chuỗi col chứa chữ cái thường, trong đó col[i] đại diện cho màu của nút thứ i (0-indexed). Cũng có danh sách cạnh edges với edges[j] = (u, v) biểu thị cạnh có hướng từ u đến v.

Một đường đi hợp lệ (valid path) là chuỗi nút x_i (i = 1..k) sao cho có cạnh từ x_i đến x_i+1. Màu của đường đi là màu nút xuất hiện nhiều nhất trên đường đi đó. Bài toán: tìm giá trị màu lớn nhất (số lần xuất hiện nhiều nhất) của bất kỳ đường đi hợp lệ nào. Nếu đồ thị có chu trình (cycle) thì trả về -1.

Ví dụ: col = "aabada", edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)] → kết quả = 4 (đường 0→1→2→3→5 có 4 nút màu 'a').

Giải thuật (Topological Sort + DP)

• n = độ dài chuỗi col.
• Xây dựng graph (danh sách kề) và indegree (bậc vào) từ edges.
• Khởi tạo hàng đợi queue chứa các nút indegree = 0.
• Khởi tạo mảng DP dp[n][26] = 0. dp[u][c] = số lượng màu c trên đường đi dài nhất kết thúc tại u.
• colorvalues[i] = chỉ số bảng chữ cái của col[i] (0..25).
• Với mỗi nút u indegree=0: dp[u][colorvalues[u]] = 1, push vào queue.
• Xử lý topo: pop u, với mỗi v ∈ graph[u], cập nhật dp[v][c] = max(dp[v][c], dp[u][c] + (c == colorvalues[v])). Giảm indegree[v], nếu =0 thì push v.
• Nếu số nút visited < n → có chu trình → trả về -1.
• Trả về max(dp).

Code Python

from collections import defaultdict

def solve(col, edges):
    n = len(col)
    graph = defaultdict(list)
    indegree = defaultdict(int)
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = []
    dp = [[0] * 26 for _ in range(n)]
    colorvalues = [ord(c) - ord("a") for c in col]

    for u in range(n):
        if u not in indegree:
            queue.append(u)
            dp[u][colorvalues[u]] = 1

    visited = 0
    while queue:
        u = queue.pop()
        visited += 1
        for v in graph[u]:
            for c in range(26):
                dp[v][c] = max(dp[v][c], dp[u][c] + (c == colorvalues[v]))
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
                del indegree[v]

    if visited < n:
        return -1
    return max(max(row) for row in dp)

col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))  # Output: 4

Đầu vào / Đầu ra

Input: "aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
Output: 4