点击获取AI摘要

1857. 有向图中最大颜色值 H

给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。

给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的颜色（下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aⱼ, bⱼ] 表示从节点 aⱼ 到节点 bⱼ 有一条 有向边 。

图中一条有效路径是一个点序列 x₁ -> x₂ -> x₃ -> ... -> xₖ ，对于所有 1 <= i < k ，从 xᵢ 到 xᵢ₊₁ 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。

请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。

示例 1：

示例1

输入：colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 “a” 的节点（上图中的红色节点）。

示例 2：

示例2

输入：colors = “a”, edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。

提示：

n == colors.length
m == edges.length
1 <= n <= 10⁵
0 <= m <= 10⁵
colors 只含有小写英文字母。
0 <= aⱼ, bⱼ < n

问题分析

给定一个有向图，包含 $n$ 个节点和 $m$ 条边，节点编号从 $0$ 到 $n - 1$ 。每个节点 $i$ 有一个小写英文字母颜色 $colors[i]$ 。定义一条有效路径为节点序列 $x_1 \to x_2 \to \dots \to x_k$ ，要求对于所有 $1 \le i < k$ ，存在从 $x_i$ 到 $x_{i+1}$ 的有向边。路径的“颜色值”是指在该路径中出现次数最多的颜色的节点数目。需要计算所有有效路径中最大的颜色值，如果图中含有环则返回 $-1$ 。

环检测：如果图中存在环，就无法构造有效的拓扑排序，题目要求遇到环时直接返回 $-1$ 。
最大颜色值：对于每一条有效路径，统计路径上每种颜色出现的次数，取出现次数最多的那种颜色。我们要在所有路径中找一个最大值。
颜色种类有限：颜色均为小写字母，共计 26 种。因此可以为每个节点维护一个长度为 26 的数组，记录到达该节点的所有路径中，各颜色出现次数的最大值。

需要解决的关键点：

如何检测有向图中的环？
如何高效地统计每个节点的“到达该节点时，各颜色出现次数的最大值”？
计算完毕后，如何得到整个图中有效路径的最大颜色值？

算法思路

构建邻接表与入度数组
- 用 adj[u] 存储节点 $u$ 的所有出边目标节点。
- 用 indegree[v] 记录节点 $v$ 的入度。
定义 DP 状态
- 令 $dp[v][c]$ 表示：在所有能够到达节点 $v$ 的有效路径中，颜色编号为 $c$ （ $0$ 对应 'a'$, …, $25$ 对应 ‘z’`）的最大出现次数。
- 整体维护一个二维数组 dp，大小为 $n \times 26$ ，初始全部置 $0$ 。
拓扑排序+DP 传播（Kahn 算法）
- 将所有 indegree[i] == 0 的节点入队，同时令其对应颜色索引处 $dp[i][color\_index(i)] = 1$ ，因为空路径到达自己时，自己颜色出现次数至少为 $1$ 。
- 维护 visited_count = 0，表示已经从队列中取出的节点数量；维护 answer = 0，表示当前全局最大的颜色值。
- 循环直到队列为空：
  1. 弹出队首节点 u，visited_count += 1；
  2. 更新全局答案：
    $answer = \max\bigl(answer,\ \max_{0 \le c < 26} dp[u][c]\bigr)\,.$
  3. 对于每条出边 $(u \to v)$ $(u \to v)$ ：
    - 颜色计数继承+合并
      1
      2
      for c in 0..25:
      dp[v][c] = max(dp[v][c], dp[u][c])
      然后单独处理节点 v 本身的颜色：
      1
      2
      cidx_v = ord(colors[v]) - ord('a')
      dp[v][cidx_v] = max(dp[v][cidx_v], dp[u][cidx_v] + 1)
    - 将 indegree[v] -= 1，若变为 0，则 v 入队。
- 结束后，如果 visited_count < n，说明有环，返回 -1；否则返回 answer。
- 为什么要用拓扑排序？
  只有在一个无环有向图（DAG）中，才能按拓扑顺序依次保证“任意一条边的前驱节点”先处理，才能正确地将前驱的 DP 结果传递到后继节点。
- 如何检测环？
  Kahn 算法的特性：如果存在环，则存在至少一个节点的入度永远无法被减为 0，最终队列出队的节点总数 visited_count 会小于 $n$ 。因此，只需检验 visited_count < n 即可判断有环。
- 为什么 DP 数组大小为 $n \times 26$ ？
  题目要求路径的“颜色值”是路径中出现次数最多的那种颜色。颜色种类共 26 种，以字母映射到 $0 \ldots 25$ 。为了对每个节点记录“到达该节点时，每种颜色的最大出现次数”，需要 26 维空间。
- 复杂度分析
  - 构建邻接表与入度： $O(m)$ 。
  - 初始化 DP：将所有元素置 0 并对入度为 0 的节点赋初值，需 $O(26 \times n)$ 。
  - 拓扑排序主循环：每个节点恰好出队一次，合计 $n$ 次；对于每个节点 $u$ ，要遍历其所有出边，共计 $m$ 条边。每条边需要将 $u$ 的 26 维数组合并到 $v$ ，需要 $O(26)$ 操作，总计 $O(26 \times m)$ 。
  - 合并总计：
    $O\bigl(26n + 26m + n + m\bigr) \;=\; O\bigl((n + m)\times 26\bigr)\;=\; O(n + m)\,,$
    其中常数因子 26 可以视为常数。
- 空间复杂度
  - 邻接表： $O(n + m)$
  - 入度数组： $O(n)$
  - DP 数组： $O(26n)$
  - 队列：最坏 $O(n)$
  - 合计： $O(n + m)$

注意：

DP 更新顺序与方式

在合并时，必须先将 $dp[u][c]$ 与 $dp[v][c]$ 逐维比较、取最大，然后单独把节点 v 自身的颜色对应的那一维加 $1$ 。若顺序颠倒或漏掉“+1”逻辑，会导致统计错误。

环检测逻辑

一定要统计拓扑排序中“实际出队”的节点数 visited_count。若 visited_count < n，则必须返回 -1，切勿返回错误的 answer。

数组越界或者字符映射错误

颜色字符映射到 0…25 索引时，务必使用 ord(colors[i]) - ord('a')，且保证 colors 中只含小写字母。

时间复杂度

构建邻接表与入度： $O(m)$
初始化 DP： $O(26 \times n)$
拓扑排序与 DP 传播： $O(n) + O\bigl(m \times 26\bigr) = O(26m + n)$
合并后：
$T(n,m) \;=\; O\bigl(26n + 26m + n + m\bigr) \;=\; O\bigl((n + m)\times 26\bigr) \;=\; O(n + m)\,.$
空间复杂度： $O(n + m + 26n) = O(n + m)$ 。

代码分解

导入必要模块与类型声明
1
2
from collections import deque
from typing import List
- deque 用于实现队列，支持 $O(1)$ 的入队出队操作。
- List 用于类型注释。

Solution 类与函数签名

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        # n: 节点数量
        n = len(colors)

colors 是一个长度为 $n$ 的字符串，edges 是长度为 $m$ 的二维列表。

构建邻接表与入度数组
1
2
3
4
5
adj = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
adj[u].append(v)
indegree[v] += 1
- 用邻接表 adj[u] 存储所有从 $u$ 出发的边。
- indegree[v] 在遍历边时累加，表示节点 $v$ 的入度大小。
初始化 DP 数组
1
dp = [[0] * 26 for _ in range(n)]
- dp[v][c] 初始为 $0$ 。
- 后续将在“入度为 0 的节点”处将其颜色对应维度设为 $1$ 。

拓扑排序队列初始化

q = deque()
for i in range(n):
    if indegree[i] == 0:
        q.append(i)
        cidx = ord(colors[i]) - ord('a')
        dp[i][cidx] = 1

所有入度为 $0$ 的节点入队，且把它们自己本身的颜色出现次数记为 $1$ 。

拓扑排序主循环与 DP 传播

visited_count = 0
answer = 0
   
while q:
    u = q.popleft()
    visited_count += 1
   
    # 更新全局最大颜色值
    answer = max(answer, max(dp[u]))
   
    for v in adj[u]:
        # 逐维比较，取 u 的各颜色计数和 v 目前各颜色计数的最大值
        for c in range(26):
            if dp[u][c] > dp[v][c]:
                dp[v][c] = dp[u][c]
   
        # 单独处理 v 节点自身的颜色 +1
        cidx_v = ord(colors[v]) - ord('a')
        dp[v][cidx_v] = max(dp[v][cidx_v], dp[u][cidx_v] + 1)
   
        # 更新 v 的入度，若为 0，则入队
        indegree[v] -= 1
        if indegree[v] == 0:
            q.append(v)

每次取出节点 u，意味着可以“确定”它的 dp[u][*]。
对于每条出边 (u -> v)，先将 u 的 26 维向量与 v 对应维度取最大值，再对 v 本身的颜色那一维做 +1。
减少 indegree[v]，若变为 0，将 v 放入队列。
同时实时维护全局 answer，取 max(dp[u])。

环检测与返回结果

# 拓扑排序结束后，如果 visited_count < n，则有环
if visited_count < n:
    return -1
   
return answer

代码实现

from collections import deque, defaultdict
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. 初始化 DP 数组
        #    dp[v][c] 表示「到达节点 v 的所有有效路径中，颜色编号 c 出现的最大次数」。
        #    颜色编号 c = ord(colors[v]) - ord('a')
        # --------------------------------------------
        # 注意：dp 初始化为全 0，大多数节点在被「拓扑入队」之前是 0。但是对于最初入度为 0 的节点 u，
        #       它自己本身就出现了一次 colors[u]，所以需要让 dp[u][ color_index(u) ] = 1。
        dp = [ [0]*26 for _ in range(n) ]

        # --------------------------------------------
        # 3. 拓扑排序（Kahn 算法）
        # --------------------------------------------
        q = deque()
        # 先将所有 indegree == 0 的节点入队
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)
                cidx = ord(colors[i]) - ord('a')
                dp[i][cidx] = 1

        visited_count = 0
        answer = 0

        while q:
            u = q.popleft()
            visited_count += 1
            # 在「确认节点 u」时，就可以尝试更新全局 answer
            # 因为 dp[u][*] 已经是「到达 u 的所有路径中，各颜色出现次数的最大值」
            answer = max(answer, max(dp[u]))  # 更新全局最大

            # 对 u 的每一条出边 (u -> v)，将 u 的状态「传播」到 v
            for v in adj[u]:
                # 将 u 的颜色计数「分发」到 v
                for c in range(26):
                    # 先把 v 目前已有的 dp[v][c] 与来自 u 的 dp[u][c] 做比较，取较大者
                    if dp[u][c] > dp[v][c]:
                        dp[v][c] = dp[u][c]
                # 然后再专门处理 v 自身颜色：相当于加 1
                cidx_v = ord(colors[v]) - ord('a')
                # “+1”只计入 v 本身的颜色出现
                dp[v][cidx_v] = max(dp[v][cidx_v], dp[u][cidx_v] + 1)

                # v 的入度减 1，如果变成 0 则入队
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)

            # 继续下一个拓扑节点
        # end while

        # --------------------------------------------
        # 4. 检测是否有环：如果有环，则 visited_count < n
        # --------------------------------------------
        if visited_count < n:
            # 说明有某些节点没被「取出」，即存在环
            return -1

        # 如果无环，answer 已经在遍历过程中维护过
        return answer