T1857.有向图中最大颜色值

topological sort, dp, https://leetcode.cn/problems/largest-color-value-in-a-directed-graph/

给你一个 有向图 ，它含有 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.length
m == edges.length
1 <= n <= 10^5
0 <= m <= 10^5
colors 只含有小写英文字母。
0 <= aj, bj < n

题面：在有向图中寻找路径使得节点颜色出现次数最大值最大

思路：拓扑排序+动态规划，维护每个节点各颜色出现次数的最大值

python

from collections import deque
from typing import List

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        # 1. 构建邻接表和入度数组
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        
        for u, v in edges:
            adj[u].append(v)
            indegree[v] += 1
        
        # 2. 初始化队列，将所有入度为0的节点加入
        q = deque([i for i in range(n) if indegree[i] == 0])
        
        # 3. DP 数组: dp[i][j] 表示以节点 i 结尾的路径中，颜色 j 出现的最大次数
        # 颜色映射: 'a' -> 0, ..., 'z' -> 25
        dp = [[0] * 26 for _ in range(n)]
        
        processed_count = 0
        ans = 0
        
        while q:
            u = q.popleft()
            processed_count += 1
            
            # 处理当前节点 u 的颜色
            u_color = ord(colors[u]) - ord('a')
            dp[u][u_color] += 1
            
            # 更新全局最大值
            ans = max(ans, dp[u][u_color])
            
            # 遍历邻居节点
            for v in adj[u]:
                # 状态转移：将 u 的所有颜色状态传递给 v
                # 因为只有 26 种颜色，这个循环是常数级的，不会超时
                for c in range(26):
                    if dp[u][c] > dp[v][c]:
                        dp[v][c] = dp[u][c]
                
                # 拓扑排序逻辑
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        
        # 4. 判断是否有环
        if processed_count < n:
            return -1
            
        return ans

下面提供一种基于 拓扑排序 + 动态规划 的做法，时间复杂度 O(n×26+m)，空间复杂度 O(n×26+m)：

构建入度数组 统计每个节点的入度 indeg，并同时把图用邻接表表示。
初始化 DP 表 用 dp[u][c] 表示以节点 u 为终点、且颜色为第 c（用 0…25 表示）的路径中，该颜色出现的最大次数。初始时，对每个节点 u：
python
```
dp[u][colors[u]] = 1
```
其它颜色都是 0。
拓扑排序遍历
- 将所有入度为 0 的节点加入队列。
- 依次从队列中取出节点 u，对每一条 u→v 边，尝试松弛：
  python
```
for c in range(26):
    dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v] == c))
```
  然后将 indeg[v] 减 1，若变为 0 则加入队列。
检查环 如果最终被处理（出队）的节点数少于 n，说明图中有环，直接返回 −1。
答案在所有 u、所有颜色 c 中取 dp[u][c] 的最大值。

python

from collections import deque
from typing import List

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        # 1. 构建图与入度
        g = [[] for _ in range(n)]
        indeg = [0] * n
        for u, v in edges:
            g[u].append(v)
            indeg[v] += 1

        # 2. 初始化 DP 表
        # dp[u][c] = 在以 u 结尾的路径中，颜色 c 出现的最大次数
        dp = [[0] * 26 for _ in range(n)]
        for u, ch in enumerate(colors):
            dp[u][ord(ch) - ord('a')] = 1

        # 3. 拓扑排序
        q = deque(u for u in range(n) if indeg[u] == 0)
        visited = 0
        ans = 0

        while q:
            u = q.popleft()
            visited += 1
            # 更新全局最优
            ans = max(ans, max(dp[u]))
            for v in g[u]:
                # 对 v 的每一种颜色尝试松弛
                for c in range(26):
                    # 如果 v 的颜色恰好是 c，则要 +1，否则不加
                    dp[v][c] = max(dp[v][c], dp[u][c] + (ord(colors[v]) - ord('a') == c))
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)

        # 4. 如果没遍历完所有节点，说明存在环
        if visited < n:
            return -1

        return ans

复杂度分析：

构建图和入度：O(m)
初始化 DP：O(n)
拓扑过程：每条边会导致一次对长度为 26 的数组松弛，整体 O(m×26)；每个节点还要一次 O(26) 的局部最值计算，总体 O(n×26)。
总体 O((n+m)×26)，在 n,m≤105 下完全可行。

这样就能在线性时间内检测环并求出最大颜色值路径。

T1857.有向图中最大颜色值 ​

T1857.有向图中最大颜色值