[Java/Python 3] 2 codes:Topological sort & DFS, w/ brief explanation and comments.
Topological Sort\n\n1. Build graph from parent to kids, and compute in-degree for each node;\n2. Use topological to get direct parent and all ancestors of the d
**Topological Sort**\n\n1. Build graph from parent to kids, and compute in-degree for each node;\n2. Use topological to get direct parent and all ancestors of the direct parent of each node;\n\n```java\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        \n        // Build graph, and compute in degree.\n        int[] inDegree = new int[n];\n        Map<Integer, List<Integer>> parentToKids = new HashMap<>();\n        for (int[] e : edges) {\n            parentToKids.computeIfAbsent(e[0], l -> new ArrayList<>()).add(e[1]);\n            ++inDegree[e[1]];\n        }\n        \n        // 1. Use a list of sets to save ancestors \n        // and to avoid duplicates.\n        // 2. Use a Queue to save 0-in-degree nodes as\n        // the starting nodes for topological sort.\n        List<Set<Integer>> sets = new ArrayList<>();\n        Queue<Integer> q = new LinkedList<>();\n        for (int i = 0; i < n; ++i) {\n            sets.add(new HashSet<>());\n            if (inDegree[i] == 0)\n                q.offer(i);\n        }\n        \n        // BFS to their neighbors and decrease \n        // the in degrees, when reaching 0, add\n        // it into queue;\n        // During this procedure, get direct parent, add \n        // all ancestors of direct parents\' of each kid.\n        while (!q.isEmpty()) {\n            int parent = q.poll();\n            for (int kid : parentToKids.getOrDefault(parent, Arrays.asList())) {\n                sets.get(kid).add(parent);\n                sets.get(kid).addAll(sets.get(parent));\n                if (--inDegree[kid] == 0)\n                    q.offer(kid);\n            }\n        }\n        \n        // Sort ancestors and put into return list. \n        List<List<Integer>> ans = new ArrayList<>();\n        for (Set<Integer> set : sets)\n            ans.add(new ArrayList<>(new TreeSet<>(set)));\n        return ans;\n    }\n```\n```python\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n         \n        # Build graph, compute in degree and\n        # get direct parent for each node.   \n        ans = [set() for _ in range(n)]\n        in_degree = [0] * n\n        parent_to_kids = defaultdict(set)\n        for parent, kid in edges:\n            ans[kid].add(parent)\n            parent_to_kids[parent].add(kid)\n            in_degree[kid] += 1\n            \n        # Use Topological sort to get direct parent\'s all ancestors    \n        dq = deque([u for u, degree in enumerate(in_degree) if degree == 0])\n        while dq:\n            parent = dq.popleft()\n            for kid in parent_to_kids[parent]:\n                ans[kid].update(ans[parent])\n                in_degree[kid] -= 1\n                if in_degree[kid] == 0:\n                    dq.append(kid)\n        return [sorted(s) for s in  ans]    \n```\n\n----\n\n**DFS**\n\n**Q & A**\n*Q1*: In the DFS approach how are we sorting the sublists?\n*A1*: \n1) The recursion sequence of the dfs method \nand \n2) the traversal sequence in the last for loop in the `getAncestors` method \n\nguarantee that the ancestor list is sorted during adding process.\n\nYou can print out the methods names and nodes number to verify it.\n\n----\n\n\n1. Build graph from parent to kids, and save `n` empty list into return List `ans`; \n2. Traverse all nodes; for each node, recurse to the lowest offspring; During recursion, add the ancestor into the corresponding ancestors list for each offspring;\n3. The recursion terminates once the the ancestor list ends with current ancestor.\n\n```java\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        Map<Integer, List<Integer>> parentToKids = new HashMap<>();\n        for (int[] e : edges) {\n            parentToKids.computeIfAbsent(e[0], l -> new ArrayList<>()).add(e[1]);\n        }\n        List<List<Integer>> ans = new ArrayList<>();\n        for (int i = 0; i < n; ++i) {\n            ans.add(new ArrayList<>());\n        }\n        for (int i = 0; i < n; ++i) {\n            dfs(i, i, ans, parentToKids);\n        }\n        return ans;\n    }\n    private void dfs(int ancestor, int kid, List<List<Integer>> ans, Map<Integer, List<Integer>> parentToKids) {\n        List<Integer> ancestors = ans.get(kid);\n        if (ancestors.isEmpty() || ancestors.get(ancestors.size() - 1) != ancestor) {\n            if (ancestor != kid) {\n                ancestors.add(ancestor);\n            }\n            for (int grandKid : parentToKids.getOrDefault(kid, Arrays.asList())) {\n                dfs(ancestor, grandKid, ans, parentToKids);\n            }\n        }\n    }\n```\n```python\n   def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        \n        def dfs(ancestor: int, kid: int) -> None:\n            if not (ans[kid] and ans[kid][-1] == ancestor):\n                if kid != ancestor:\n                    ans[kid].append(ancestor)\n                for grand_child in parent_to_kids[kid]:\n                    dfs(ancestor, grand_child)\n\n        parent_to_kids = defaultdict(list)\n        for parent, kid in edges:\n            parent_to_kids[parent].append(kid)\n        ans = [[] for _ in range(n)]\n        for i in range(n):\n            dfs(i, i)\n        return ans\n```\n\n**Analysis for both methods:**\n\nTime & space: `O(n ^ 2 + E)`, where `E = # of edges`.\n\n----\n\nPlease free feel to ask if you have any questions, and **Upovte** if it is helpful. Thanks.
['Java', 'Python3']