数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：在有向图中查找最大颜色值
假设我们有一个包含 n 个彩色节点和 m 个不同边的有向图。节点编号从 0 到 n-1。我们有一个字符串 col，其中包含小写字母，col[i] 表示该图中第 i 个节点的颜色（从 0 开始索引）。我们还有一个边列表，其中 edges[j] = (u, v) 表示 u 和 v 之间有一条边。
图中的一条有效路径是从 1 到 k 的所有 i 的节点 xi 序列，使得从 xi 到 xi+1 存在一条有向边。路径的颜色是该路径中最常出现的节点颜色。我们必须找到该图中任何有效路径的最大颜色值。如果图中存在循环，则返回 -1。
因此，如果输入类似于 col = "aabada" edges = [(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 按字母顺序排列的顺序
对于 u 从 0 到 n - 1，执行以下操作：
如果 u 不在 indegree 中，则
将 u 插入到队列的末尾
dp[u, colorvalues[u]] := 1
visited := 0
当队列不为空时，执行以下操作：
u := 队列的第一个元素，并将其删除
visited := visited + 1
对于 graph[u] 中的每个 v，执行以下操作：
对于 c 从 0 到 25，执行以下操作：
dp[v, c] = dp[v, c] 和 (dp[u, c] + (如果 c 与 colorvalues[v] 相同，则为 1，否则为 0)) 的最大值
indegree[v] := indegree[v] - 1
如果 indegree[v] 等于 0，则
将 v 插入到队列的末尾
删除 indegree[v]
如果 visited < 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
284 次查看
