BinarySearch 0427 Longest Path in a Graph

Problem statement

https://binarysearch.com/problems/Longest-Path-in-a-Graph/

Solution

Because it is DAG, we can use dp here: dp(node) is the longest path ending with node.

Complexity

It is O(E) for time and O(n) for space.

Code

class Solution:
    def solve(self, G):
        @lru_cache(None)
        def dp(node):
            if not G[node]: return 0
            return max(dp(neib) for neib in G[node]) + 1

        return max(dp(i) for i in range(len(G)))