💯✅🔥Easy Java ,Python3 ,C++ Solution|| 63 ms ||≧◠‿◠≦✌
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the approach is to use a DFS to traverse the graph and find the an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the approach is to use a DFS to traverse the graph and find the ancestors of each node. By starting the DFS from each node and adding the current node to the ans list of its children, we ensure that all the ancestors of a node are recorded in the ans list of that node.\nThe directChild list is used to keep track of the direct children of each node, which helps in efficiently traversing the graph during the DFS.\n\n---\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach used in the code is a depth-first search (DFS) to find the ancestors of each node in the graph represented by the given edges.\n- **Initialize two lists**: ans to store the ancestors of each node, and directChild(dc) to store the direct children of each node.\nIterate through the edges list and add each child node to the directChild(dc) list of its parent node.\n- Iterate through the nodes from 0 to n-1 and perform a DFS starting from each node.\n- In the DFS function, for each child node of the current node, check if the current node is not already present in the ans list of the child node. If not, add the current node to the ans list of the child node and recursively call the DFS function with the child node as the new current node.\n- Return the ans list as the final result.\n---\n# Complexity\n- Time complexity:O(V + E)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n---\n- Space complexity:O(V + E)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n---\n# Code\n```java []\nclass Solution {\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n    List<List<Integer>> ans = new ArrayList();\n    List<List<Integer>> dc = new ArrayList();\n    for (int i = 0; i < n; i++) {\n        ans.add(new ArrayList());\n        dc.add(new ArrayList());\n    }\n    for (int[] e: edges) \n        dc.get(e[0]).add(e[1]);\n    for (int i = 0; i < n; i++) \n        dfs(i, i, ans, dc);\n    return ans;\n}\nprivate void dfs(int x, int curr, List<List<Integer>> ans, List<List<Integer>> dc) {\n    for (int ch: dc.get(curr))\n        if(ans.get(ch).size() == 0 || ans.get(ch).get(ans.get(ch).size() - 1) != x) {\n            ans.get(ch).add(x);\n            dfs(x, ch, ans, dc);\n        }\n}\n}\n```\n```python3 []\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        ans = [[] for _ in range(n)]\n        directChild = [[] for _ in range(n)]\n        for e in edges:\n            directChild[e[0]].append(e[1])\n        for i in range(n):\n            self.dfs(i, i, ans, directChild)\n        return ans\n\n    def dfs(self, x: int, curr: int, ans: List[List[int]], directChild: List[List[int]]) -> None:\n        for ch in directChild[curr]:\n            if not ans[ch] or ans[ch][-1] != x:\n                ans[ch].append(x)\n                self.dfs(x, ch, ans, directChild)\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> ans(n), directChild(n);\n        for (auto& e : edges) {\n            directChild[e[0]].push_back(e[1]);\n        }\n        for (int i = 0; i < n; i++) {\n            dfs(i, i, ans, directChild);\n        }\n        return ans;\n    }\n\nprivate:\n    void dfs(int x, int curr, vector<vector<int>>& ans, vector<vector<int>>& directChild) {\n        for (int ch : directChild[curr]) {\n            if (ans[ch].empty() || ans[ch].back() != x) {\n                ans[ch].push_back(x);\n                dfs(x, ch, ans, directChild);\n            }\n        }\n    }\n};\n```\n---\n![upvote.png](https://assets.leetcode.com/users/images/e6f4f26f-a7f5-465b-8ec1-aa665db072f9_1719537871.6475258.png)\n\n\n\n
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'C++', 'Java', 'Python3']