Topological Sort - Largest Color Value in a Directed Graph
Examine the following code snippet for the largest color value problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.
from collections import defaultdict, deque
def largestPathValue(colors, edges):
n = len(colors)
graph = defaultdict(list)
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])
count = 0
max_color_value = 0
while queue:
node = queue.popleft()
count += 1
c_index = ord(colors[node]) - ord('a')
dp[node][c_index] += 1
max_color_value = max(max_color_value, dp[node][c_index])
for nei in graph[node]:
for i in range(26):
dp[nei][i] = max(dp[nei][i], dp[node][i])
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
if count != n:
return -1 # cycle detected
return max_color_value
