Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def maxPathValue(n, m, edges, values):
- adj = [[] for i in range(n+1)]
- inDegree = [0 for i in range(n+1)]
- for i in range(m):
- adj[edges[i][0]].append(edges[i][1])
- inDegree[edges[i][1]] += 1
- q = []
- dp = [[0 for i in range(26)] for j in range(n + 1)]
- for i in range(1, n + 1):
- if (inDegree[i] == 0):
- q.append(i)
- popCounts = 0
- ans = 0
- while (len(q) > 0):
- curr = q.pop(0)
- popCounts += 1
- num = ord(values[curr - 1]) - 97
- dp[curr][num] += 1
- ans = max(ans, dp[curr][num])
- for i in adj[curr]:
- for j in range(26):
- dp[i][j] = max(dp[i][j], dp[curr][j])
- inDegree[i] -= 1
- if (inDegree[i] == 0):
- q.append(i)
- if (popCounts == n):
- break
- if (len(q) > 0 or popCounts < n):
- return -1
- return ans
Advertisement
Add Comment
Please, Sign In to add comment