✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS - Depth First Search
\n\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n *
![Screenshot 2024-06-29 093230.png](https://assets.leetcode.com/users/images/75d292a2-95af-41a5-ac95-01badb22b1cc_1719633796.3382638.png)\n\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n\nhttps://youtu.be/Gt9mP2rl8Ts\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2400 Subscribers*\n*Current Subscribers: 2348*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn a Directed Acyclic Graph (DAG), determining the ancestors of each node involves identifying all nodes from which there is a directed path to the given node. The ancestors of a node \\( v \\) are those nodes \\( u \\) such that there exists a path from \\( u \\) to \\( v \\). Since the graph is acyclic, this problem can be efficiently solved using Depth-First Search (DFS).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Graph Representation:**\n   - Use an adjacency list to represent the graph. This allows efficient traversal of the graph.\n\n2. **DFS for Ancestor Tracking:**\n   - Perform a DFS from each node to identify all nodes that can reach the current node. During this traversal, mark nodes as visited to avoid cycles and repeated work.\n   - While performing the DFS, if we reach a node, we add the starting node (ancestor) to the list of ancestors for the reached node.\n\n3. **Result Collection:**\n   - Initialize a list of lists to store the ancestors for each node. Each index corresponds to a node and contains a list of its ancestors.\n\n4. **Sorting:**\n   - After collecting all ancestors using DFS, sort the ancestor lists to meet the requirement of ascending order.\n\n# Complexity\n- **Time Complexity:**\n  - Building the graph: \\( O(m) \\), where \\( m \\) is the number of edges.\n  - DFS from each node: \\( O(n \u22C5 (n + m)) \\) in the worst case, where \\( n \\) is the number of nodes and \\( m \\) is the number of edges. Each DFS can traverse up to all nodes and edges.\n  - Sorting the ancestors: \\( O(n  \u22C5  k log k) \\), where \\( k \\) is the average number of ancestors per node.\n  \n  The overall time complexity is \\( O(n  \u22C5  (n + m)) \\) considering the nested DFS traversal.\n\n- **Space Complexity:**\n  - Storing the graph: \\( O(n + m) \\).\n  - Storing the ancestors: \\( O(n  \u22C5  n) \\) in the worst case if every node is an ancestor of every other node.\n  - Additional space for recursion stack in DFS: \\( O(n) \\).\n\n\n# Step By Step Explanation\nLet\'s break down the process using tables for Example 1:\n\n**Input:**\n```plaintext\nn = 8\nedges = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n```\n\n**Graph Representation:**\n```plaintext\nNode | Adjacent Nodes\n---------------------\n0    | [3, 4]\n1    | [3]\n2    | [4, 7]\n3    | [5, 6, 7]\n4    | [6]\n5    | []\n6    | []\n7    | []\n```\n\n**DFS Traversal and Ancestors Collection:**\n1. Start DFS from node 0:\n   - Reach nodes: 3, 4, 5, 6, 7\n   - Update ancestors for these nodes.\n   \n2. Start DFS from node 1:\n   - Reach nodes: 3, 5, 6, 7\n   - Update ancestors for these nodes.\n   \n3. Start DFS from node 2:\n   - Reach nodes: 4, 6, 7\n   - Update ancestors for these nodes.\n   \n4. Continue for other nodes similarly.\n\n**Collected Ancestors (Before Sorting):**\n```plaintext\nNode | Ancestors\n---------------------\n0    | []\n1    | []\n2    | []\n3    | [0, 1]\n4    | [0, 2]\n5    | [0, 1, 3]\n6    | [0, 1, 2, 3, 4]\n7    | [0, 1, 2, 3]\n```\n\n**Sorted Ancestors:**\n```plaintext\nNode | Ancestors (Sorted)\n-------------------------\n0    | []\n1    | []\n2    | []\n3    | [0, 1]\n4    | [0, 2]\n5    | [0, 1, 3]\n6    | [0, 1, 2, 3, 4]\n7    | [0, 1, 2, 3]\n```\n\nThis approach ensures that all ancestors are collected and sorted correctly for each node in the DAG.\n\n\n\n# Code\n```java []\nclass Solution {\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<List<Integer>> res = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            res.add(new ArrayList<>());\n        }\n\n        ArrayList<Integer>[] graph = new ArrayList[n];\n        for (int i = 0; i < n; i++) {\n            graph[i] = new ArrayList<>();\n        }\n        for (int[] edge : edges) {\n            graph[edge[0]].add(edge[1]);\n        }\n\n        for (int i = 0; i < n; i++) {\n            dfs(graph, i, i, res, new boolean[n]);\n        }\n\n        for (int i = 0; i < n; i++) {\n            res.get(i).sort(Integer::compareTo);\n        }\n\n        return res;\n    }\n\n    private void dfs(ArrayList<Integer>[] graph, int parent, int curr, List<List<Integer>> res, boolean[] visit) {\n        visit[curr] = true;\n        for (int dest : graph[curr]) {\n            if (!visit[dest]) {\n                res.get(dest).add(parent);\n                dfs(graph, parent, dest, res, visit);\n            }\n        }\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> res(n);\n        vector<vector<int>> graph(n);\n        \n        for (const auto& edge : edges) {\n            graph[edge[0]].push_back(edge[1]);\n        }\n        \n        for (int i = 0; i < n; ++i) {\n            vector<bool> visit(n, false);\n            dfs(graph, i, i, res, visit);\n        }\n        \n        for (int i = 0; i < n; ++i) {\n            sort(res[i].begin(), res[i].end());\n        }\n        \n        return res;\n    }\n\nprivate:\n    void dfs(vector<vector<int>>& graph, int parent, int curr, vector<vector<int>>& res, vector<bool>& visit) {\n        visit[curr] = true;\n        for (int dest : graph[curr]) {\n            if (!visit[dest]) {\n                res[dest].push_back(parent);\n                dfs(graph, parent, dest, res, visit);\n            }\n        }\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def getAncestors(self, n, edges):\n        res = [[] for _ in range(n)]\n        graph = [[] for _ in range(n)]\n        \n        for edge in edges:\n            graph[edge[0]].append(edge[1])\n        \n        for i in range(n):\n            self.dfs(graph, i, i, res, [False] * n)\n        \n        for i in range(n):\n            res[i].sort()\n        \n        return res\n    \n    def dfs(self, graph, parent, curr, res, visit):\n        visit[curr] = True\n        for dest in graph[curr]:\n            if not visit[dest]:\n                res[dest].append(parent)\n                self.dfs(graph, parent, dest, res, visit)\n        \n```\n```JavaScript []\nvar getAncestors = function(n, edges) {\n    let res = Array.from({ length: n }, () => []);\n    let graph = Array.from({ length: n }, () => []);\n    \n    for (let edge of edges) {\n        graph[edge[0]].push(edge[1]);\n    }\n    \n    for (let i = 0; i < n; i++) {\n        dfs(graph, i, i, res, Array(n).fill(false));\n    }\n    \n    for (let i = 0; i < n; i++) {\n        res[i].sort((a, b) => a - b);\n    }\n    \n    return res;\n};\n\nfunction dfs(graph, parent, curr, res, visit) {\n    visit[curr] = true;\n    for (let dest of graph[curr]) {\n        if (!visit[dest]) {\n            res[dest].push(parent);\n            dfs(graph, parent, dest, res, visit);\n        }\n    }\n}\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/45a130ab-5593-4402-a2f2-17a98644875d_1719633811.7502232.png)\n
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'Python', 'C++', 'Java', 'JavaScript']