# Untitled

Oct 28th, 2021
576
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. def maxPathValue(n, m, edges, values):
3.     adj = [[] for i in range(n+1)]
4.
5.     inDegree = [0 for i in range(n+1)]
6.
7.     for i in range(m):
9.         inDegree[edges[i][1]] += 1
10.
11.     q = []
12.
13.     dp = [[0 for i in range(26)] for j in range(n + 1)]
14.
15.     for i in range(1, n + 1):
16.         if (inDegree[i] == 0):
17.             q.append(i)
18.
19.     popCounts = 0
20.     ans = 0
21.
22.     while (len(q) > 0):
23.         curr = q.pop(0)
24.         popCounts += 1
25.
26.         num = ord(values[curr - 1]) - 97
27.         dp[curr][num] += 1
28.         ans = max(ans, dp[curr][num])
29.
31.
32.             for j in range(26):
33.                 dp[i][j] = max(dp[i][j], dp[curr][j])
34.
35.             inDegree[i] -= 1
36.
37.             if (inDegree[i] == 0):
38.                 q.append(i)
39.
40.         if (popCounts == n):
41.             break
42.
43.
44.     if (len(q) > 0 or popCounts < n):
45.         return -1
46.
47.     return ans
RAW Paste Data