# 1857. Largest Color Value in a Directed Graph

• Time: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{edges}|$
• Space: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{edges}|$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public: int largestPathValue(string colors, vector>& edges) { const int n = colors.length(); int ans = 0; int processed = 0; vector> graph(n); vector inDegree(n); queue q; vector> count(n, vector(26)); // Build graph for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; graph[u].push_back(v); ++inDegree[v]; } // Topology for (int i = 0; i < n; ++i) if (inDegree[i] == 0) q.push(i); while (!q.empty()) { const int out = q.front(); q.pop(); ++processed; ans = max(ans, ++count[out][colors[out] - 'a']); for (const int in : graph[out]) { for (int i = 0; i < 26; ++i) count[in][i] = max(count[in][i], count[out][i]); if (--inDegree[in] == 0) q.push(in); } } return processed == n ? ans : -1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public int largestPathValue(String colors, int[][] edges) { final int n = colors.length(); int ans = 0; int processed = 0; List[] graph = new List[n]; int[] inDegree = new int[n]; int[][] count = new int[n][26]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); // Build graph for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; graph[u].add(v); ++inDegree[v]; } // Topology Queue q = IntStream.range(0, n) .filter(i -> inDegree[i] == 0) .boxed() .collect(Collectors.toCollection(ArrayDeque::new)); while (!q.isEmpty()) { final int out = q.poll(); ++processed; ans = Math.max(ans, ++count[out][colors.charAt(out) - 'a']); for (final int in : graph[out]) { for (int i = 0; i < 26; ++i) count[in][i] = Math.max(count[in][i], count[out][i]); if (--inDegree[in] == 0) q.offer(in); } } return processed == n ? ans : -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution: def largestPathValue(self, colors: str, edges: List[List[int]]) -> int: n = len(colors) ans = 0 processed = 0 graph = [[] for _ in range(n)] inDegree = [0] * n q = collections.deque() count = [[0] * 26 for _ in range(n)] # Build graph for u, v in edges: graph[u].append(v) inDegree[v] += 1 # Vpology for i, degree in enumerate(inDegree): if degree == 0: q.append(i) while q: u = q.popleft() processed += 1 count[u][ord(colors[u]) - ord('a')] += 1 ans = max(ans, count[u][ord(colors[u]) - ord('a')]) for v in graph[u]: for i in range(26): count[v][i] = max(count[v][i], count[u][i]) inDegree[v] -= 1 if inDegree[v] == 0: q.append(v) return ans if processed == n else -1