Topological Sort - Largest Color Value in a Directed Graph
Review the following Python snippet for the largest color value problem. Identify the bug that causes incorrect results:
def largest_color_value(colors, edges):
from collections import deque
n = len(colors)
graph = [[] for _ in range(n)]
indegree = [0]*n
for u,v in edges:
graph[u].append(v)
indegree[v] += 1
dp = [[0]*26 for _ in range(n)]
queue = deque([i for i in range(n) if indegree[i] == 0])
while queue:
node = queue.popleft()
dp[node][ord(colors[node]) - ord('a')] += 1
for nei in graph[node]:
for c in range(26):
dp[nei][c] = max(dp[nei][c], dp[node][c])
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
return max(max(row) for row in dp)