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" edge =[（0,1）、（1,4）、（1,2）、（2,3）、（3,5）、（4,5）のような場合]、

その場合、出力は4になります。0-> 1-> 2-> 3-> 5は、色が「a」の最長パスを持っているためです。

これを解決するには、次の手順に従います-

• n：=列のサイズ

• グラフ：=エッジリストから指定されたグラフ

• indegree：=ノードとそのin-degree値を含むマップ

• queue：=新しいリスト

• dp：=サイズn x 26の配列を作成し、0で埋めます

• colorvalues：=列のすべてのcについて、アルファベットのcの順序でリストを作成します

• 0からn-1の範囲のuの場合、実行

  • uが学位を取得していない場合は、

    • キューの最後にuを挿入します

    • dp [u、colorvalues [u]]：=1

• 訪問済み：=0

• キューが空でないときに、実行します

  • u：=キューの前の要素で、後で削除します

  • 訪問済み：=訪問済み+ 1

  • グラフ[u]の各vについて、実行

    • 0から25の範囲のcの場合、実行

      • dp [v、c] =dp [v、c]および（dp [u、c] +の最大値（cがcolorvalues [v]と同じ場合は1、それ以外の場合は0）

    • indegree [v]：=indegree [v]-1

    • indegree [v]が0と同じ場合、

      • キューの最後にvを挿入します

      • デルインディグリー[v]

• 訪問した場合

  • -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