✏️ Beats 💯100% || Only ❷ Steps ||  Fastest ✈️ Easy ♻️ || Detailed Explanation ✅
\uD83C\uDF89 Screenshot \uD83D\uDCF8\n\n\n\n## Input \uD83D\uDCE5 \n\n    1. One n which denotes the number of nodes of Directed Acyclic Graph\n\n    2. 2D arra
# \uD83C\uDF89 Screenshot \uD83D\uDCF8\n\n![2192.png](https://assets.leetcode.com/users/images/fcc214db-5a6b-45e8-be1f-98c1f8ec861d_1719626368.76604.png)\n\n## Input \uD83D\uDCE5 \n\n    1. One n which denotes the number of nodes of Directed Acyclic Graph\n\n    2. 2D array which repesent our edges \n\n    3. Note edges[i].length is 2\n\n## Output \uD83D\uDCE4\n\n    We have to submit our new array that will content every ancestor\n\n    of every node\n\n# Example \uD83D\uDCDC\n\n![2192 que 1 new.png](https://assets.leetcode.com/users/images/8d4a71dc-09c8-4eda-be84-66bb0ed419a3_1719626821.0981202.png)\n\n\n    `Ex.` \n\n        We have 8 nodes from 0 to 7 \n\n        We need to find every node from which we can reach our Ith node\n\n        1. To 0 = [] cause we can not go to node 0 from no node\n\n        2. To 1 = [] same logic as 0\n\n        3. To 2 = [] same logic as 1\n\n        4. To 3 = [0, 1] we can reach 3 from 0 and 1 \n\n        5. To 4 = [0, 2] from 0 and 2\n\n        6. To 5 = [0, 1, 3] from 0 , 1 and 3\n\n        7. To 6 = [0, 1, 2, 3, 4] from 0, 1, 2, 3 and 4  \n\n        8. To 7 = [0, 1, 2, 3] from 0, 1, 2 and 3\n\n        We got our que now let discuss approach and code too\n\n        \n\n# Approach \u270D\uD83C\uDFFC\n\n    Step 1 -> We will build our own graph in which we will store\n\n        Destinations of every node mean \n\n            We store by Ith node we can which node\n\n        Ex. we have edegs we rebuild it \n\n        \uD83D\uDD39edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n\n        \uD83D\uDD39graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n    Step 2 -> We will make a Func that will push ancestor \n\n        now Graph[I] will be our info of ancestor \n\n        We know that for I = 0 Graph[0] = [3, 4]\n\n        We know 3 and 4 have a ancestor 0 so We will push 0 for\n\n        3 and 4 Simple \n\n# Step wise Explanation \uD83E\uDE9C\n\n    There will be 4 steps as we seen above\n\n    Step 1 \u27A4 Making our own graph \n\n    Step 2 \u27A4 Call our dfs that append ancestor \n\n    Step 3 \u27A4 Submit our ancestor\n\n## \uD83D\uDCCC Step 1\uFE0F\u20E3 \n\n    \uD83D\uDD39 In 2D array at every edges[i][0] we will push our edges[i][1]\n\n    \uD83D\uDD39 Cause edges[i][0] is ancestor of edges[i][1] \n\n    \uD83D\uDD39 [0,3] -> 0 is ancestor of 3\n\n    \uD83D\uDD39 [1,4] -> 1 is ancestor of 4\n\n\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        // making 2D array\n        vector<vector<int>> ancestors(n);\n        vector<vector<int>> graph(n);\n        // edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n        for (auto& edge : edges) {\n            graph[edge[0]].push_back(edge[1]);\n        }\n        //* graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n    }\n};\n\n```\n``` JAVA []\nclass Solution {\n\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n         //making 2D array\n        List<List<Integer>> ancestors = new ArrayList<>(n);\n        List<List<Integer>> graph = new ArrayList<>(n);\n\n        for (int i = 0; i < n; i++) {\n            ancestors.add(new ArrayList<>());\n            graph.add(new ArrayList<>());\n        }\n        // edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n        for (int[] edge : edges) {\n            graph.get(edge[0]).add(edge[1]);\n        }\n        // * graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n    }\n}\n```\n``` JAVASCRIPT []\nvar getAncestors = function (n, edges) {\n    // making 2D array\n    let ancestors = Array.from({ length: n }, () => []);\n    let graph = Array.from({ length: n }, () => []);\n\n    // edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n    for (let edge of edges) {\n        graph[edge[0]].push(edge[1]);\n    }\n    //* graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n};\n```\n```PYTHON []\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        # making 2D array\n        ancestors = [[] for _ in range(n)]\n        graph = [[] for _ in range(n)]\n\n        # edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n\n        for edge in edges:\n            graph[edge[0]].append(edge[1])\n\n        # * graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n```\n\n## \uD83D\uDCCC Step 2\uFE0F\u20E3 \n\n    \uD83D\uDD39 making our dfs Function \n\n    \uD83D\uDD39 Work is simple apply loop for 1 to N \n\n    \uD83D\uDD39 Get the array of Ith and traverse it \n\n    \uD83D\uDD39 Go to that values and push the index \n\n    \uD83D\uDD39 We know that for I = 0 Graph[0] = [3, 4]\n\n         We know 3 and 4 have a ancestor 0 so We will push 0 for\n\n         3 and 4 Simple \n\n\n\n```C++ []\n    void dfs(vector<vector<int>>& graph, int i, int j,\n             vector<vector<int>>& ancestors) {\n        // get tha list of ancestors at index j mean that will be ancestors of our index i\n        for (auto& g : graph[j]) {\n            // checking if empty or last elem is not same elem means \n            // 0 is not the ancestor of 0\n            if (ancestors[g].empty() || ancestors[g].back() != i) {\n                // push back into our array\n                ancestors[g].push_back(i);\n                // call for next element\n                dfs(graph, i, g, ancestors);\n            }\n        }\n    }\n\n```\n``` JAVA []\n    private void dfs(List<List<Integer>> graph, int i, int j, List<List<Integer>> ancestors) {\n        // get tha list of ancestors at index j mean that will be ancestors of our index i\n        for (int g : graph.get(j)) {\n            // checking if empty or and last elem is not same elem\n            //  means 0 is not the ancestor of 0\n            if (ancestors.get(g).isEmpty() || ancestors.get(g).get(ancestors.get(g).size() - 1) != i) {\n                // push back into our array\n                ancestors.get(g).add(i);\n                // call for next element\n                dfs(graph, i, g, ancestors);\n            }\n        }\n    }\n```\n``` JAVASCRIPT []\nconst dfs = function (graph, i, j, ancestors) {\n    // get tha list of ancestors at index j mean that will be ancestors of our index i\n    for (let g of graph[j]) {\n        // checking if empty or last elem is not same elem means \n        // 0 is not the ancestor of 0\n        if (!ancestors[g].length || ancestors[g][ancestors[g].length - 1] !== i) {\n            // push back into our array\n            ancestors[g].push(i);\n            // call for next element\n            dfs(graph, i, g, ancestors);\n        }\n    }\n}\n```\n```PYTHON []\n    def dfs(self, graph, i, j, ancestors):\n        # get tha list of ancestors at index j mean that will be ancestors of our index i\n        for g in graph[j]:\n            # checking if empty or last elem is not same elem \n            # means 0 is not the ancestor of 0\n            if not ancestors[g] or ancestors[g][-1] != i:\n                # push back into our array\n                ancestors[g].append(i)\n                # call for next element\n                self.dfs(graph, i, g, ancestors)\n```\n\n## \uD83D\uDCCC Step 3\uFE0F\u20E3\n\n    \uD83D\uDD39 calling our dfs Function and SUBMIT \uD83D\uDE80\n\n```C++ []\n    // We call our function for every index o to N\n    // call with our graph and index and index of list of ancestor\n    // and our ans ancestors \n    for (int i = 0; i < n; i++) {\n        dfs(graph, i, i, ancestors);\n    }\n\n    return ancestors;\n```\n``` JAVA []\n    // We call our function for every index o to N\n    // call with our graph and index and index of list of ancestor\n    // and our ans ancestors \n    for (int i = 0; i < n; i++) {\n        dfs(graph, i, i, ancestors);\n    }\n\n    return ancestors;\n```\n``` JAVASCRIPT []\n    // We call our function for every index o to N\n    // call with our graph and index and index of list of ancestor\n    // and our ans ancestors \n    for (let i = 0; i < n; i++) {\n        dfs(graph, i, i, ancestors);\n    }\n\n    return ancestors;\n};\n```\n```PYTHON []\n    # We call our function for every index o to N\n    # call with our graph and index and index of list of ancestor\n    # and our ans ancestors \n    for i in range(n):\n        self.dfs(graph, i, i, ancestors)\n\n    return ancestors\n\n```\n\n \n# Complexity \uD83C\uDFD7\uFE0F\n- \u231A Time complexity: $$O(n^2)$$ `n given`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- \uD83E\uDDFA Space complexity: $$O(n^2)$$ `For making ancestor array`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n\n```C++ []\nclass Solution {\n    void dfs(vector<vector<int>>& graph, int i, int j,\n             vector<vector<int>>& ancestors) {\n        // get tha list of ancestors at index j mean that \n        // will be ancestors of our index i\n        for (auto& g : graph[j]) {\n            // checking if empty or last elem is not same elem\n            // means 0 is not the ancestor of 0\n            if (ancestors[g].empty() || ancestors[g].back() != i) {\n                // push back into our array\n                ancestors[g].push_back(i);\n                // call for next element\n                dfs(graph, i, g, ancestors);\n            }\n        }\n    }\n\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> ancestors(n);\n        vector<vector<int>> graph(n);\n\n        // edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n\n        for (auto& edge : edges) {\n            graph[edge[0]].push_back(edge[1]);\n        }\n\n        //* graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n        // We call our function for every index o to N\n        // call with our graph and index and index of list of ancestor\n        // and our ans ancestors \n        for (int i = 0; i < n; i++) {\n            dfs(graph, i, i, ancestors);\n        }\n\n        return ancestors;\n    }\n};\n```\n``` JAVA []\nclass Solution {\n\n    private void dfs(List<List<Integer>> graph, int i, int j, List<List<Integer>> ancestors) {\n        // get tha list of ancestors at index j mean that \n        // will be ancestors of our index i\n        for (int g : graph.get(j)) {\n            // checking if empty or last elem is not same elem\n            // means 0 is not the ancestor of 0\n            if (ancestors.get(g).isEmpty() || ancestors.get(g).get(ancestors.get(g).size() - 1) != i) {\n                // push back into our array\n                ancestors.get(g).add(i);\n                // call for next element\n                dfs(graph, i, g, ancestors);\n            }\n        }\n    }\n\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<List<Integer>> ancestors = new ArrayList<>(n);\n        List<List<Integer>> graph = new ArrayList<>(n);\n\n        for (int i = 0; i < n; i++) {\n            ancestors.add(new ArrayList<>());\n            graph.add(new ArrayList<>());\n        }\n\n        // edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n\n        for (int[] edge : edges) {\n            graph.get(edge[0]).add(edge[1]);\n        }\n\n        // * graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n        // We call our function for every index o to N\n        // call with our graph and index and index of list of ancestor\n        // and our ans ancestors \n        for (int i = 0; i < n; i++) {\n            dfs(graph, i, i, ancestors);\n        }\n\n        return ancestors;\n    }\n}\n```\n``` JAVASCRIPT []\nconst dfs = function (graph, i, j, ancestors) {\n    // get tha list of ancestors at index j mean \n    //that will be ancestors of our index i\n    for (let g of graph[j]) {\n        // checking if empty or last elem is not same elem \n        // means 0 is not the ancestor of 0\n        if (!ancestors[g].length\n            || ancestors[g][ancestors[g].length - 1] !== i) {\n            // push back into our array\n            ancestors[g].push(i);\n            // call for next element\n            dfs(graph, i, g, ancestors);\n        }\n    }\n}\n\nvar getAncestors = function (n, edges) {\n    let ancestors = Array.from({ length: n }, () => []);\n    let graph = Array.from({ length: n }, () => []);\n\n    // edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n\n    for (let edge of edges) {\n        graph[edge[0]].push(edge[1]);\n    }\n\n    //* graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n    // We call our function for every index o to N\n    // call with our graph and index and index of list of ancestor\n    // and our ans ancestors \n    for (let i = 0; i < n; i++) {\n        dfs(graph, i, i, ancestors);\n    }\n\n    return ancestors;\n};\n```\n```PYTHON []\nclass Solution:\n\n    def dfs(self, graph, i, j, ancestors):\n        for g in graph[j]:\n            # checking if already added and last elem is not same elem \n            # means 0 is not the ancestor of 0\n            if not ancestors[g] or ancestors[g][-1] != i:\n                # push back into our array\n                ancestors[g].append(i)\n                # call for next element\n                self.dfs(graph, i, g, ancestors)\n\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        ancestors = [[] for _ in range(n)]\n        graph = [[] for _ in range(n)]\n\n        # edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n\n        for edge in edges:\n            graph[edge[0]].append(edge[1])\n\n        # * graph = [[3, 4], [3], [4, 7], [5, 6, 7], [6]]\n\n        # We call our function for every index o to N\n        # call with our graph and index and index of list of ancestor\n        # and our ans ancestors \n        for i in range(n):\n            self.dfs(graph, i, i, ancestors)\n\n        return ancestors\n\n```\n\n---\n# \uD83E\uDD42\u2728\uD83E\uDDC1 More solution \uD83C\uDF89\uD83C\uDF82\u2728\uD83C\uDF70\uD83E\uDD73 \n\n## Go To My Profile and access my GIT [Prakhar-002](https://leetcode.com/u/Prakhar-002/)\n\n## JAVA \uD83C\uDF41| PYTHON \uD83C\uDF70| JAVASCRIPT\u2603\uFE0F | C++ \uD83C\uDFB2| C \uD83D\uDC96\n\n![image.png](https://assets.leetcode.com/users/images/9a0e870e-bf06-4276-bb80-c72e42cbbbf1_1719631882.225308.png)\n\n\n\n
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'C++', 'Java', 'Python3', 'JavaScript']