Hard
题目描述
有一个由 n 个彩色节点和 m 条边组成的有向图。节点编号从 0 到 n - 1。
给你一个字符串 colors，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的颜色（下标从 0 开始）。同时给你一个二维数组 edges，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条有向边。
图中一条有效路径是一个节点序列 x1 -> x2 -> x3 -> ... -> xk，使得对于每个 1 <= i < k，都存在一条从 xi 到 xi+1 的有向边。路径的颜色值是该路径上出现次数最多的颜色的节点数量。
返回给定图中任意有效路径的最大颜色值，如果图中包含环则返回 -1。
示例 1:
输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 包含 3 个颜色为 "a" 的节点。
示例 2:
输入：colors = "a", edges = [[0,0]]
输出：-1
解释：从 0 到 0 存在一个环。
约束条件:
n == colors.lengthm == edges.length1 <= n <= 10^50 <= m <= 10^5colors由小写英文字母组成0 <= aj, bj < n
解题思路
这是一道结合拓扑排序和动态规划的经典题目。
核心思路：
- 环检测：使用拓扑排序检测图中是否存在环，如果有环则无法计算最长路径
- 动态规划状态定义：
dp[u][c]表示从节点u开始的路径中，颜色c的最大出现次数 - 状态转移：对于每个节点
u和每种颜色c，通过其所有后继节点更新状态
算法步骤：
- 构建邻接表和入度数组
- 使用 Kahn 算法进行拓扑排序，同时进行动态规划
- 在拓扑排序过程中，对每个节点维护 26 种颜色的最大值
- 当处理节点
u时，如果节点颜色是c，则dp[u][c]至少为 1 - 遍历节点
u的所有邻居v，更新dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v] == c ? 1 : 0))
时间复杂度优化： 由于只有 26 种颜色，我们可以为每个节点维护一个大小为 26 的数组，在拓扑排序的过程中逐步更新这些值。
这种方法既保证了环的检测，又能高效地计算出所有路径中各颜色的最大出现次数。
代码实现
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.length();
vector<vector<int>> graph(n);
vector<int> indegree(n, 0);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
indegree[edge[1]]++;
}
// dp[i][j] represents max count of color j starting from node i
vector<vector<int>> dp(n, vector<int>(26, 0));
queue<int> q;
// Initialize nodes with indegree 0
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
dp[i][colors[i] - 'a'] = 1;
}
}
int processed = 0;
int maxColorValue = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
processed++;
// Update max color value
for (int c = 0; c < 26; c++) {
maxColorValue = max(maxColorValue, dp[u][c]);
}
for (int v : graph[u]) {
// Update dp values for neighbor v
for (int c = 0; c < 26; c++) {
int colorCount = dp[u][c] + (colors[v] - 'a' == c ? 1 : 0);
dp[v][c] = max(dp[v][c], colorCount);
}
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
// Check if there's a cycle
return processed == n ? maxColorValue : -1;
}
};
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
graph = [[] for _ in range(n)]
indegree = [0] * n
for a, b in edges:
graph[a].append(b)
indegree[b] += 1
# dp[i][j] represents max count of color j starting from node i
dp = [[0] * 26 for _ in range(n)]
queue = []
# Initialize nodes with indegree 0
for i in range(n):
if indegree[i] == 0:
queue.append(i)
dp[i][ord(colors[i]) - ord('a')] = 1
processed = 0
max_color_value = 0
while queue:
u = queue.pop(0)
processed += 1
# Update max color value
max_color_value = max(max_color_value, max(dp[u]))
for v in graph[u]:
# Update dp values for neighbor v
for c in range(26):
color_count = dp[u][c] + (1 if ord(colors[v]) - ord('a') == c else 0)
dp[v][c] = max(dp[v][c], color_count)
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
# Check if there's a cycle
return max_color_value if processed == n else -1
public class Solution {
public int LargestPathValue(string colors, int[][] edges) {
int n = colors.Length;
List<int>[] graph = new List<int>[n];
int[] indegree = new int[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (int[] edge in edges) {
graph[edge[0]].Add(edge[1]);
indegree[edge[1]]++;
}
// dp[i][j] represents max count of color j starting from node i
int[,] dp = new int[n, 26];
Queue<int> queue = new Queue<int>();
// Initialize nodes with indegree 0
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.Enqueue(i);
dp[i, colors[i] - 'a'] = 1;
}
}
int processed = 0;
int maxColorValue = 0;
while (queue.Count > 0) {
int u = queue.Dequeue();
processed++;
// Update max color value
for (int c = 0; c < 26; c++) {
maxColorValue = Math.Max(maxColorValue, dp[u, c]);
}
foreach (int v in graph[u]) {
// Update dp values for neighbor v
for (int c = 0; c < 26; c++) {
int colorCount = dp[u, c] + (colors[v] - 'a' == c ? 1 : 0);
dp[v, c] = Math.Max(dp[v, c], colorCount);
}
indegree[v]--;
if (indegree[v] == 0) {
queue.Enqueue(v);
}
}
}
// Check if there's a cycle
return processed == n ? maxColorValue : -1;
}
}
var largestPathValue = function(colors, edges) {
const n = colors.length;
const graph = Array(n).fill().map(() => []);
const indegree = Array(n).fill(0);
for (const [a, b] of edges) {
graph[a].push(b);
indegree[b]++;
}
// dp[i][j] represents max count of color j starting from node i
const dp = Array(n).fill().map(() => Array(26).fill(0));
const queue = [];
// Initialize nodes with indegree 0
for (let i = 0; i < n; i++) {
if (indegree[i]
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(V + E) × 26 = O(26(V + E))，其中 V 是节点数，E 是边数。拓扑排序需要 O(V + E)，每个节点需要更新 26 种颜色的状态 |
| 空间复杂度 | O(V × 26 + E) = O(26V + E)，用于存储 DP 数组、邻接表和队列 |