Basic Intuitive Python Solution
Intuition\nThe key insight is to traverse each node\'s ancestors recursively and gather all unique ancestors. By sorting nodes based on the number of their dire
# Intuition\nThe key insight is to traverse each node\'s ancestors recursively and gather all unique ancestors. By sorting nodes based on the number of their direct parents, we can build the ancestor list incrementally, ensuring that all dependencies are considered in the correct order.\n# Approach\n1. **Build Adjacency List**: Start by building an adjacency list `d` where each key represents a node and its value is a list of nodes that point to it (parents).\n   \n2. **Sort Nodes by Number of Parents**: Sort nodes based on the length of their parent lists. This ensures that nodes with fewer parents are processed first.\n\n3. **Compute Ancestors**: Initialize a dictionary `s` to store ancestors. Iterate through sorted nodes. For each node `i`, use a queue (`q`) to perform a breadth-first search (BFS)-like traversal starting from its parents. This ensures that all ancestors are collected, including those of newly discovered ancestors.\n\n4. **Store and Sort Ancestors**: Store the sorted ancestors in the `ans` list at the index corresponding to each node.\n\n# Complexity\n- Time complexity: O(n + e)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        d = defaultdict(list)\n        ans = [[]]*n\n        for i in edges:\n            d[i[1]].append(i[0])\n\n        keys = sorted(d.keys(), key= lambda k: len(d[k]))\n\n        s = defaultdict(set)\n        for i in keys:\n            q = []\n            q.extend(d[i])\n            while q:\n                t = q.pop(0)\n                if t not in s[i]:\n                    s[i].add(t)\n                    q.extend(d[t])\n            ans[i] = sorted(s[i])   \n            \n        return ans\n\n```
['Breadth-First Search', 'Sorting', 'Python', 'Python3']