在 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”的最长路径。

示例

让我们看看以下实现以更好地理解

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