🔥🔥Beats 100% | Easy Solution with explanation in java,c++,python
Explanation\nsolution []\nans = [[], [], [], []]\ndirectChild = [[1, 2], [], [3], []]\n\n# DFS Traversal:\n\n- From node 0:\n0 -> 1: Add 0 to ancestors of 1.\n1
# Explanation\n```solution []\nans = [[], [], [], []]\ndirectChild = [[1, 2], [], [3], []]\n```\n# DFS Traversal:\n\n- From node 0:\n0 -> 1: Add 0 to ancestors of 1.\n1 -> 3: Add 0 to ancestors of 3.\n0 -> 2: Add 0 to ancestors of 2.\n2 -> 3: 3 already has 0 as an ancestor.\nFrom node 1:\n1 -> 3: Add 1 to ancestors of 3.\nFrom node 2:\n2 -> 3: Add 2 to ancestors of 3.\nFinal ans:\n```solution []\nans = [  [],     // Ancestors of 0\n  [0],    // Ancestors of 1\n  [0],    // Ancestors of 2\n  [0, 1, 2] // Ancestors of 3\n]\n\n```\n\n\n\n# Code\n\n```java []\npublic List<List<Integer>> getAncestors(int n, int[][] edges) {\n    List<List<Integer>> ans = new ArrayList();\n    List<List<Integer>> directChild = new ArrayList();\n    for (int i = 0; i < n; i++) {\n        ans.add(new ArrayList());\n        directChild.add(new ArrayList());\n    }\n    for (int[] e: edges) \n        directChild.get(e[0]).add(e[1]);\n    for (int i = 0; i < n; i++) \n        dfs(i, i, ans, directChild);\n    return ans;\n}\nprivate void dfs(int x, int curr, List<List<Integer>> ans, List<List<Integer>> directChild) {\n    for (int ch: directChild.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, directChild);\n        }\n}\n```\n```python []\ndef getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n    direct_child = defaultdict(list)\n    ans = [[] for _ in range(n)]\n    for x, y in edges:\n        direct_child[x].append(y)\n\n    def dfs(x, curr):\n        for ch in direct_child[curr]:\n            if ans[ch] and ans[ch][-1] == x: continue\n            ans[ch].append(x)\n            dfs(x, ch) \n\n    for i in range(n): dfs(i, i)\n    return ans\n```\n```c++ []\nvector<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    for(int i = 0; i < n; i++)\n        dfs(i, i, ans, directChild);\n    return ans;\n}\nvoid dfs(int x, int curr, vector<vector<int>>& ans, vector<vector<int>>& directChild) {\n    for (auto& ch: directChild[curr]) \n        if(ans[ch].size() == 0 || ans[ch].back() != x) {\n            ans[ch].push_back(x);\n            dfs(x, ch, ans, directChild);\n        }\n}\n```\n![e6f4f26f-a7f5-465b-8ec1-aa665db072f9_1719537871.6475258.png](https://assets.leetcode.com/users/images/71fd8e84-8d0f-403f-ae7a-2baa2a4bb256_1719633580.3698165.png)\n
['Depth-First Search', 'C++', 'Java', 'Python3']