Pythonでノードを繰り返さずにDAGで最長のパスの長さを見つけるプログラム

隣接リストで表される有向非巡回グラフが1つあるとします。ノードを繰り返さずに、グラフ内で最長のパスを見つける必要があります。

したがって、入力が次のような場合

パスが0->1->3-> 4-> 2、長さが4であるため、出力は4になります。

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

• ans：=0
• n：=グラフのノード数
• table：=サイズnのリストで、-1で埋めます
• 関数dfs（）を定義します。これには時間がかかります
• table [u]が-1でない場合、
  • リターンテーブル[u]
• p_len：=0
• グラフ[u]の各vectexvについて、
  を実行します。
  • p_len：=最大p_lenおよび（1 + dfs（v））
• table [u]：=p_len
• return p_len
• メインメソッドから次の手順を実行します-
• 0からnの範囲のiについては、
  • ans：=ansの最大値、dfs（i）
• 回答を返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, graph):
      ans = 0
      n = len(graph)
      table = [-1] * n
      def dfs(u):
         if table[u] != -1:
            return table[u]
         p_len = 0
         for v in graph[u]:
            p_len = max(p_len, 1 + dfs(v))
         table[u] = p_len
         return p_len
      for i in range(n):
         ans = max(ans, dfs(i))
      return ans
ob = Solution()
graph = [
   [1, 2],
   [3, 4],
   [],
   [4],
   [2],
]
print(ob.solve(graph))

入力

graph = [[1, 2],[3, 4],[],[4],[2]]

出力

4