th0m45s5helby

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):
  8.         adj[edges[i][0]].append(edges[i][1])
  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.  
  30.         for i in adj[curr]:
  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