from collections import deque, defaultdict
class Solution:
def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
n = len(colors)
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
# color_count[node][color] = max count of color along any path ending at node
color_count = [ [0]*26 for _ in range(n) ]
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
for i in range(n):
color_count[i][ord(colors[i])-ord('a')] = 1
visited = 0
answer = 0
while queue:
node = queue.popleft()
visited += 1
for c in range(26):
answer = max(answer, color_count[node][c])
for nei in graph[node]:
for c in range(26):
color_count[nei][c] = max(color_count[nei][c], color_count[node][c] + (1 if c == ord(colors[nei])-ord('a') else 0))
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
return answer if visited == n else -1
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
vector<vector<int>> graph(n);
vector<int> indegree(n, 0);
for (auto& e : edges) {
graph[e[0]].push_back(e[1]);
indegree[e[1]]++;
}
vector<vector<int>> color_count(n, vector<int>(26, 0));
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) q.push(i);
color_count[i][colors[i] - 'a'] = 1;
}
int visited = 0, answer = 0;
while (!q.empty()) {
int node = q.front(); q.pop();
visited++;
for (int c = 0; c < 26; ++c)
answer = max(answer, color_count[node][c]);
for (int nei : graph[node]) {
for (int c = 0; c < 26; ++c) {
int add = (c == colors[nei] - 'a') ? 1 : 0;
color_count[nei][c] = max(color_count[nei][c], color_count[node][c] + add);
}
indegree[nei]--;
if (indegree[nei] == 0)
q.push(nei);
}
}
return visited == n ? answer : -1;
}
};
import java.util.*;
class Solution {
public int largestPathValue(String colors, int[][] edges) {
int n = colors.length();
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[n];
for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
indegree[e[1]]++;
}
int[][] colorCount = new int[n][26];
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) queue.add(i);
colorCount[i][colors.charAt(i) - 'a'] = 1;
}
int visited = 0, answer = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
visited++;
for (int c = 0; c < 26; ++c)
answer = Math.max(answer, colorCount[node][c]);
for (int nei : graph.get(node)) {
for (int c = 0; c < 26; ++c) {
int add = (c == colors.charAt(nei) - 'a') ? 1 : 0;
colorCount[nei][c] = Math.max(colorCount[nei][c], colorCount[node][c] + add);
}
indegree[nei]--;
if (indegree[nei] == 0)
queue.add(nei);
}
}
return visited == n ? answer : -1;
}
}
/**
* @param {string} colors
* @param {number[][]} edges
* @return {number}
*/
var largestPathValue = function(colors, edges) {
const n = colors.length;
const graph = Array.from({length: n}, () => []);
const indegree = Array(n).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
indegree[v]++;
}
const colorCount = Array.from({length: n}, () => Array(26).fill(0));
const queue = [];
for (let i = 0; i < n; ++i) {
if (indegree[i] === 0) queue.push(i);
colorCount[i][colors.charCodeAt(i) - 97] = 1;
}
let visited = 0, answer = 0;
while (queue.length) {
const node = queue.shift();
visited++;
for (let c = 0; c < 26; ++c)
answer = Math.max(answer, colorCount[node][c]);
for (const nei of graph[node]) {
for (let c = 0; c < 26; ++c) {
colorCount[nei][c] = Math.max(colorCount[nei][c], colorCount[node][c] + (c === colors.charCodeAt(nei) - 97 ? 1 : 0));
}
indegree[nei]--;
if (indegree[nei] === 0)
queue.push(nei);
}
}
return visited === n ? answer : -1;
};
You are given a directed graph with n nodes, labeled from 0 to n - 1. Each node is assigned a color, represented by a lowercase English letter in the string colors (where colors[i] is the color of node i). The graph's edges are given as a list edges, where each edge is a pair [u, v] indicating a directed edge from node u to node v.
Your task is to find the largest number of nodes with the same color that can be found on any path in the graph. If the graph contains a cycle, return -1 (since a path could be infinitely long).
Key constraints:
-1.The core of this problem is to find, for every path in the directed graph, the maximum count of any single color that appears on that path. However, the presence of cycles complicates things, since cycles could allow us to revisit nodes indefinitely and artificially inflate counts.
A brute-force approach might be to enumerate all possible paths and count the colors along each one, but this is computationally infeasible due to the exponential number of paths in a graph, especially with cycles.
Instead, we notice that if we process the graph in topological order (i.e., from sources to sinks, only visiting nodes after all their dependencies), we can efficiently propagate color counts along all possible paths. This way, for each node, we can keep track of the maximum count of each color that can be achieved along any path ending at that node.
Detecting cycles is also crucial. If the graph contains a cycle, it's impossible to determine a finite maximum, so we must return -1 in that case.
The solution uses a combination of topological sorting and dynamic programming to efficiently compute the answer.
-1.
This approach ensures each node and edge is processed only once, and color counts are updated efficiently using dynamic programming.
Example Input:
colors = "abaca"
edges = [[0,1],[0,2],[2,3],[3,4]]
This problem demonstrates how to combine topological sorting and dynamic programming to efficiently compute path statistics in a directed graph. By carefully propagating color counts and detecting cycles, we avoid the pitfalls of brute-force enumeration and ensure correctness even in complex graphs. The use of a color count table at each node is the key insight that makes the solution both elegant and efficient.