用 Python 编写程序，在有向图中查找最大颜色值
假设我们有一个有向图，其中有 n 个颜色节点和 m 条不同的边。节点编号从 0 到 n-1。我们有一个小写字母的字符串 col，其中 col[i] 表示此图中第 i 个节点的颜色(从 0 开始)。我们还有一个边列表，其中 Edges[j] = (u, v) 表示 u 和 v 之间存在一条边。
图中的有效路径是所有 i 从 1 到 k 的节点 xi 序列，这样从 xi 到 xi+1 存在一条有向边。路径的颜色是该路径中最常见的节点颜色。我们必须找到该图中任何有效路径的最大颜色值。如果图中有一个循环，则返回 -1。
因此，如果输入类似 col = "aabada"边 = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)],
那么输出将是 4，因为 0 -> 1 -> 2 -> 3 -> 5 具有颜色为"a"的最长路径。
为了解决这个问题，我们将遵循以下步骤 −
n:= col 的大小
graph:= 给定边列表中的图
indegree:= 包含节点及其入度值的映射
queue:= 一个新列表
dp:= 创建一个大小为 n x 26 的数组，并用 0 填充
colorvalues:= 为 col 中的所有 c 创建一个按字母顺序排列的列表
对于 0 到 n - 1 范围内的 u，执行
如果 u 不在入度中，则
将 u 插入队列末尾
dp[u, colorvalues[u]]:= 1
visited:= 0
当队列不为空时，执行
u:= 队列的前元素，之后删除
visited := accessed + 1
对于 graph[u] 中的每个 v，执行
对于 0 到 25 范围内的 c，执行
dp[v, c] = dp[v, c] 和 (dp[u, c] + (1 如果 c 与colorvalues[v]，否则为 0)
indegree[v] := indegree[v] - 1
如果 indegree[v] 与 0 相同，则
将 v 插入队列末尾
del indegree[v]
如果访问 < n，则
返回 -1
返回 dp 中的最大元素
示例
让我们看看下面的实现以便更好地理解
from collections import defaultdict
def solve(col, edges):
n=len(col)
graph=defaultdict(list)
indegree=defaultdict(int)
for u,v in edges:
graph[u].append(v)
indegree[v]+=1
queue=[]
dp=[[0]*26 for _ in range(n)]
colorvalues=[ord(c)-ord("a") for c in col]
for u in range(n):
if u not in indegree:
queue.append(u)
dp[u][colorvalues[u]]=1
visited=0
while queue:
u=queue.pop()
visited+=1
for v in graph[u]:
for c in range(26):
dp[v][c]=max(dp[v][c],dp[u][c] + (c==colorvalues[v]))
indegree[v]-=1
if indegree[v]==0:
queue.append(v)
del indegree[v]
if visited<n:
return -1
return max(max(x) for x in dp)
col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))
输入
"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
输出
4
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
