Reverse DFS + DP [PYTHON3] Approach - TC: O(N), SC: O(N)
Approaches\n\n## Unoptimal but First Approach\n- We can start from the root, then we go to each child while maintain a list of ancestors.\n- To do this we can u
# Approaches\n\n## _Unoptimal_ but First Approach\n- We can start from the **root**, then we **go to each child** while **maintain a list of ancestors**.\n- To do this we can use **DFS**. We create a function that takes **list of previous ancestors** and a  **child node**.\n- Then for _each root(there can be several roots)_, we will call this function, while passing an _empty list(signifying that they don\'t have any ancestors)_ for each.\n- We will create a _global list_ that contains _empty lists_ corresponding to _each node_ in the **_DAG(Directed Acyclic Graph)_**.\n- Now when the function is called, first we add all the _nodes in the ancestors list_ we are passing while calling and then we add the _child node_ to the _ancestors list_.\n- Now we iterate upon the _children of the child node_ and call **DFS** on them with the new _ancestors list_.\n- Finally we return the _global list_ after sorting the lists inside it(that\'s a condistion given in the question).\n\n## _Unoptimal_ but Second Approach\n\n- _Instead of directly searching for the roots and going down towards the leaves, we rather search for leaves, that is nodes that don\'t have any children._\n- To do so, we keep track of _parents_ of each node when creating **adjacency list** on _edges_.\n- We create a function to get ancedynstors, this will be **DFS**, but instead of **DFS on children**, we do **DFS on parents**, this is what I call **Reverse DFS**.\n- For each _node_, we create a list, put all the _parent nodes_ in it, and then we call this function on them to get the ancestors of the parents, which we add to the list. _(**NOTE**: Since this is being recursively, we are also getting ancestors for parent nodes, parent-to-parent/grand-parent nodes, and so on, until we reach to a node, which has no parents, resulting to return empty an empty list, which will be filled till it reaches the child node)_\n- Final we sort the list and save it inside another one which is there for our answer.\n- Lastly, we return our answer.\n\n## Second Approach but _Optimal_\n\n- Now, you might see that our 2 approaches are similar, but for second one, we can optimize it further.\n- To optimize the second one, we will apply **_DP(Dynamic Programming)/Memoization_** on the **DFS** function.\n- We also take the _out-degree_ while iterating on the edges when creating the **adjacency list**.\n- Now instead of calling for all nodes, we just call the function for the _leaf nodes_, or the _nodes_ which have 0 _out-degree_. (This is the **topological sorting** step, since we are only iterating over _topologically last nodes_)\n- Finally, we sort the lists that are inside our _answer list_ and return. _(**NOTE**: Instead of sorting later, we can also allow our function to return the ancestors in sorted order)_\n\n# Complexity (Optimal Approach)\n\n- **Time complexity**: $$O(n)$$ since we are just iterating once on each node.\n- **Space complexity**: $$O(n)$$ since we are storing the _answer list_ and _dp list_, both are list of n-size.\n\n# Code (Optimal Approach)\n```Python3\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        adj = [set() for i in range(n)]\n        deg = [0 for i in range(n)]\n\n        for edge in edges:\n            u, v = edge\n            adj[v].add(u)\n            deg[u] += 1\n        \n        dp = [None] * n\n        def getAnc(child):\n            if dp[child] is not None:\n                return dp[child]\n            \n            ancestors = []\n            for parent in adj[child]:\n                ancestors.append(parent)\n                ancestors.extend(getAnc(parent))\n            \n            dp[child] = sorted(set(ancestors))\n            return dp[child]\n        \n        for i in range(n):\n            if deg[i] == 0:\n                dp[i] = getAnc(i)\n        \n        return dp\n```
['Dynamic Programming', 'Depth-First Search', 'Graph', 'Topological Sort', 'Memoization', 'Python3']