🚀 Reverse Graph || DP Memoization || Step by step explain || No topological sort
Intuition\n Describe your first thoughts on how to solve this problem. \nYou need to think reversely for easily handle this problem. \nHow about reversing the g
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nYou need to think reversely for easily handle this problem. \nHow about reversing the graph and find all of the children on each node?\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStep 1: Reverse Graph -> Finding all children of node\nStep 2: DFS with cache (memoization DP)\nStep 3: Export sorted output\n\n# Complexity\n- Time complexity: O(V*log(V) + E)\n(because we need to sort output at the end)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(E)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        # Reverse Graph -> Finding all children of node\n        for i in range(len(edges)):\n            edges[i][0], edges[i][1] = edges[i][1], edges[i][0]\n        \n        graph = defaultdict(list)\n        for edge in edges:\n            graph[edge[0]].append(edge[1]) \n        cache = {}\n        # DFS with cache (memoization DP)\n        def dfs(node):\n            if node in cache: return cache[node]\n            children = set([node])\n            for next_node in graph[node]:\n                # Extend the set with all of new children\n                children |= dfs(next_node) \n            cache[node] = children\n            return cache[node]\n        res = []\n        for i in range(n):\n            res_i = dfs(i).copy()\n            res_i.remove(i) # remove its self as a child\n            res.append(sorted(list(res_i))) # output need to be sorted\n        return res\n            \n```\nI hope it help, thank for reading my solution\n\n![upvote.jfif](https://assets.leetcode.com/users/images/70db965e-139a-4254-853e-28d114ba8387_1719634393.446215.jpeg)\n\n\n\n
['Dynamic Programming', 'Memoization', 'Python3']