ปัญหา
กำหนดกราฟมีทิศทาง (Directed Graph) ที่มี n โหนดสี และ m เส้นเชื่อม โหนดหมายเลข 0 ถึง n-1 สตริง col เก็บสีของแต่ละโหนด (ตัวพิมพ์เล็ก) edges เก็บคู่ (u, v) แสดงว่ามีเส้นเชื่อมจาก u ไป v
Path ที่ถูกต้องคือลำดับโหนดที่มีเส้นเชื่อมต่อเนื่อง สีของ Path คือสีที่พบบ่อยที่สุดใน Path ต้องการหาค่าสีสูงสุด (จำนวนครั้งมากที่สุดของสีใดสีหนึ่ง) ใน Path ใดๆ หากมี Cycle ให้คืน -1
ตัวอย่าง
col = "aabada", edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
Path: 0 → 1 → 2 → 3 → 5 มีสี 'a' 4 ครั้ง → Output: 4
อัลกอริทึม (Topological Sort + DP)
- สร้าง Graph และคำนวณ In-degree ของแต่ละโหนด
- ใช้ Queue เริ่มจากโหนดที่ In-degree = 0
- DP Table:
dp[node][color] = จำนวนสีสูงสุดที่ถึงโหนดนี้ได้ - Relaxation: อัปเดต DP ตาม Topological Order
- ถ้า Visited < n → มี Cycle → คืน -1
- คืนค่า Max ใน DP Table
ตัวอย่างโค้ด
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)]
color_values = [ord(c) - ord("a") for c in col]
for u in range(n):
if u not in indegree:
queue.append(u)
dp[u][color_values[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 == color_values[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ความซับซ้อน
- Time: O(n × 26 + m × 26) ≈ O(n + m)
- Space: O(n × 26)
