在Python中查找DAG的没有重复节点的最长路径的程序

假设我们有一个由邻接表表示的有向无环图。我们必须找到图中没有节点重复的最长路径。

因此，如果输入如下所示：

那么输出将是4，因为路径是0 -> 1 -> 3 -> 4 -> 2，长度为4。

要解决这个问题，我们将按照以下步骤进行 –

ans：= 0
n：=图的节点数
table：=大小为n的列表并填充为-1
定义一个函数dfs()。这将带有u
如果table[u]不是-1，则
- 返回table[u]
p_len:= 0
对于图中的每个向量v，执行以下操作 –
- p_len：=p_len和(1+dfs(v))的最大值
table[u]：=p_len
返回p_len
从主方法执行以下操作 –
对于范围从0到n中的i，执行以下操作-
- ans：= ans和dfs(i)的最大值
返回ans

更多Python相关文章，请阅读：Python 教程

示例（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))