Python程序：在有向图中找到最大颜色值

假设我们有一个有向图，其中有 n 个带颜色的节点和 m 条不同的边缘。节点从 0 到 n-1 编号。我们有一个字符串 col，其中 col[i] 表示这个图中第 i 个节点的颜色（从 0 开始）。我们还有一个边缘列表，其中 edges[j] = (u, v) 表示 u 和 v 之间有一条边。

图中的一个有效路径是节点 xi 所有 i 从 1 至 k 的序列，其中从 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 的字母表顺序进行排序的列表

• 对于范围从 0 到 n – 1 的 u，执行以下操作：

  • 如果 u 不在 indegree 中，则
    • 将 u 插入队列的末尾

    • dp[u, colorvalues[u]]:= 1

• visited:= 0

• 当队列不为空时，执行以下操作：

  • u:= 队列的前一个元素并将其删除

  • visited := visited + 1

  • 对于图[u]中的每个 v，执行以下操作：

    • 对于范围从 0 到 25 的 c，执行以下操作：

    • dp[v,c] = dp[v,c] 的最大值和 (dp[u,c]+(1)，如果c与 v 的 colorvalues 相同，否则为 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