1.题目基本信息
1.1.题目描述
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n – 1 。
给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [a_j, b_j] 表示从节点 a_j 到节点 b_j 有一条 有向边 。
图中一条有效 路径 是一个点序列 x_1 -> x_2 -> x_3 -> … -> x_k ，对于所有 1 <= i < k ，从 x_i 到 x_i+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。
1.2.题目地址
https://leetcode.cn/problems/largest-color-value-in-a-directed-graph/description/
2.解题方法
2.1.解题思路
拓扑排序+动态规划
2.2.解题步骤
第一步，状态构建；dp[i][j]为以i节点结尾的路径的颜色j的最大数量
第二步，构建邻接表和入度表（注意初始化图，边并不一定会包括所有的节点）
第三步，先获取拓扑排序，再在过程中进行状态转移；同时获取拓扑排序的长度，用来判断有无环
- 其中，状态转移方程：dp[i][j]=max([dp[node][j]+nodeIIsJColor(j) for node in prev(i)])
- 如果拓扑排序的长度不等于总节点个数，则有环，直接返回-1
最终状态dp中的最大值即为最终的结果
3.解题代码
Python代码
from collections import defaultdict,dequeclass Solution:def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:length=len(colors)# 第一步，状态构建；dp[i][j]为以i节点结尾的路径的颜色j的最大数量dp=[[0]*26 for _ in range(length)]# 第二步，构建邻接表和入度表（注意初始化图，边并不一定会包括所有的节点）graph={i:[] for i in range(length)}inDegrees=defaultdict(int)for from_,to_ in edges:graph[from_].append(to_)inDegrees[to_]+=1# 第三步，先获取拓扑排序，再在过程中进行状态转移；同时获取拓扑排序的长度，用来判断有无环# 其中，状态转移方程：dp[i][j]=max([dp[node][j]+nodeIIsJColor(j) for node in prev(i)])topuSortArrLength=0que=deque()for node in graph.keys():if inDegrees[node]==0:que.append(node)while que:node=que.popleft()topuSortArrLength+=1dp[node][ord(colors[node])-ord('a')]+=1 # 将当前node的颜色添加到状态数组中for subNode in graph[node]:inDegrees[subNode]-=1for i in range(26): # 更新子节点的每一种颜色状态dp[subNode][i]=max(dp[subNode][i],dp[node][i])if inDegrees[subNode]==0:que.append(subNode)# 如果拓扑排序的长度不等于总节点个数，则有环，直接返回-1if topuSortArrLength!=length:return -1# print(dp)# 最终状态中的最大值即为最终的结果return max([max(t) for t in dp])
4.执行结果
