Largest Color Value in a Directed Graph
Problem
Given a directed graph with a color per node, return the max count of any single color along any path, or −1 if there is a cycle.
colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]3from collections import deque
def largest_path_value(colors, edges):
return _impl(colors, edges)
def _impl(colors, edges):
n = len(colors)
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v); indeg[v] += 1
dp = [[0] * 26 for _ in range(n)]
q = deque()
for i in range(n):
if indeg[i] == 0: q.append(i)
visited = 0
best = 0
while q:
u = q.popleft(); visited += 1
dp[u][ord(colors[u]) - 97] += 1
best = max(best, dp[u][ord(colors[u]) - 97])
for v in adj[u]:
for c in range(26):
if dp[u][c] > dp[v][c]: dp[v][c] = dp[u][c]
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return -1 if visited < n else bestfunction largestPathValue(colors, edges) {
const n = colors.length;
const adj = Array.from({length: n}, () => []);
const ind = new Array(n).fill(0);
for (const [u, v] of edges) { adj[u].push(v); ind[v]++; }
const dp = Array.from({length: n}, () => new Array(26).fill(0));
const q = [];
for (let i = 0; i < n; i++) if (ind[i] === 0) q.push(i);
let head = 0, visited = 0, best = 0;
while (head < q.length) {
const u = q[head++]; visited++;
dp[u][colors.charCodeAt(u) - 97]++;
best = Math.max(best, dp[u][colors.charCodeAt(u) - 97]);
for (const v of adj[u]) {
for (let c = 0; c < 26; c++) if (dp[u][c] > dp[v][c]) dp[v][c] = dp[u][c];
if (--ind[v] === 0) q.push(v);
}
}
return visited < n ? -1 : best;
}class Solution {
public int largestPathValue(String colors, int[][] edges) {
return solve(colors, edges); }
int solve(String colors, int[][] edges) {
int n = colors.length();
List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] ind = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); ind[e[1]]++; }
int[][] dp = new int[n][26];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (ind[i] == 0) q.add(i);
int visited = 0, best = 0;
while (!q.isEmpty()) {
int u = q.poll(); visited++;
int ci = colors.charAt(u) - 'a';
dp[u][ci]++; best = Math.max(best, dp[u][ci]);
for (int v : adj.get(u)) {
for (int c = 0; c < 26; c++) if (dp[u][c] > dp[v][c]) dp[v][c] = dp[u][c];
if (--ind[v] == 0) q.add(v);
}
}
return visited < n ? -1 : best;
}
}int largestPathValue(string colors, vector<vector<int>>& edges) { return solve(colors, edges); }
int solve(string colors, vector<vector<int>>& edges) {
int n = colors.size();
vector<vector<int>> adj(n);
vector<int> ind(n, 0);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); ind[e[1]]++; }
vector<vector<int>> dp(n, vector<int>(26, 0));
queue<int> q;
for (int i = 0; i < n; i++) if (ind[i] == 0) q.push(i);
int visited = 0, best = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); visited++;
int ci = colors[u] - 'a';
dp[u][ci]++; best = max(best, dp[u][ci]);
for (int v : adj[u]) {
for (int c = 0; c < 26; c++) if (dp[u][c] > dp[v][c]) dp[v][c] = dp[u][c];
if (--ind[v] == 0) q.push(v);
}
}
return visited < n ? -1 : best;
}Explanation
We want the largest count of a single color along any path in a directed graph, but if there's a cycle the path could be infinite, so we must return -1 in that case. Both needs are met by processing nodes in topological order using Kahn's algorithm.
Kahn's BFS starts from nodes with in-degree 0 and peels them off, decrementing neighbors' in-degrees until they too reach 0. If we manage to visited all n nodes this way, the graph is acyclic; if some are never reached, a cycle trapped them and we answer -1.
Alongside, we carry a DP table dp[v][c] = the most color-c nodes on any path that ends at v. When we pop node u, we first bump its own color count dp[u][color(u)]++ and update best. Then for each outgoing edge to v, we push u's 26 color totals forward, keeping the max into dp[v].
Processing in topo order guarantees that by the time we reach v, every path leading into it has already contributed its counts, so dp[v] is final and correct.
Example: colors = "abaca", edges [[0,1],[0,2],[2,3],[3,4]]. The path 0 → 2 → 3 → 4 collects three 'a's, so best = 3.