🐍 python, simple BFS solution with explanation; O(V+E)
Intuition\nThis is a topoligical sort problem. Here we use the famous Kahn\'s algo. \n\n# Approach\n1) Like most of the graphs problem first we create and adjac
# Intuition\nThis is a topoligical sort problem. Here we use the famous Kahn\'s algo. \n\n# Approach\n1) Like most of the graphs problem first we create and adjacency map and in_degree dictionary.\n2) Then we create a queue and add the nodes with no parent (in_degree[node]==0 or node not in_degree), we add that to the queue.\n3) We create a list of sets, which set_i contains the ancestors for node i\n4) we run a BFS to reduce the in_degree of each node we visit and once the the degree is zero we add that to the queue. Also, at each step, we update the set_i. \n\n# Complexity\n- Time complexity: O(V+E)\n\n- Space complexity: O(V+E) not including the space we need for the output. \n# Code\n```\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        adj_map = defaultdict(defaultdict)\n        in_degree = defaultdict(int)\n        for beg, end in edges:\n            adj_map[beg][end]=None\n            in_degree[end]+=1\n\n        q = deque()\n        for node in range(n):\n            if node not in in_degree:\n                q.append(node)\n\n        ans = [set() for _ in range(n)]\n        while q:\n            node = q.popleft()\n            for child in adj_map[node]:\n                in_degree[child]-=1\n                if in_degree[child]==0:\n                    q.append(child)\n                ans[child].update(ans[node] | {node})\n        return [sorted(list(i)) for i in ans]\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'Python3']