Easy Java Solution | DFS | Beats 100 💯✅
Ancestor Finder in a Directed Acyclic Graph (DAG)\n\n## Problem Statement\n\nGiven a directed acyclic graph (DAG) with n nodes, numbered from 0 to n-1, and a li
# Ancestor Finder in a Directed Acyclic Graph (DAG)\n\n## Problem Statement\n\nGiven a directed acyclic graph (DAG) with `n` nodes, numbered from `0` to `n-1`, and a list of `edges` where `edges[i] = [u, v]` indicates a directed edge from node `u` to node `v`, we aim to find all the ancestors for each node. The result should be a list of lists where the `i-th` list contains all the ancestors of the `i-th` node in sorted order.\n\n## Intuition\n\nThe key idea is to perform a Depth-First Search (DFS) starting from each node to identify all its ancestors. Since the graph is acyclic, starting from a node and performing a DFS will lead us to all the nodes from which we can reach the starting node. We record these nodes as the ancestors. By storing the results in a list of lists, we can provide the required output efficiently.\n\n## Approach\n\n1. **Graph Representation**: \n   - Represent the graph using an adjacency list. Each node will have a list of nodes from which it can be reached.\n\n2. **DFS Traversal**:\n   - For each node, perform a DFS to explore all its ancestors.\n   - Use a boolean array to keep track of visited nodes to avoid re-processing.\n\n3. **Collect Ancestors**:\n   - During the DFS traversal, collect the nodes that lead to the current node.\n   - After finishing the DFS for a node, sort the list of ancestors to meet the requirement of sorted order.\n\n4. **Result Compilation**:\n   - Compile the ancestors for each node into a list and return the final list of lists.\n\n### Detailed Steps\n\n1. **Initialize the Graph**: Create an empty adjacency list for each node.\n2. **Fill the Graph**: Populate the adjacency list using the given edges. For each edge `(u, v)`, add `u` to the adjacency list of `v`.\n3. **Perform DFS**: For each node `i` from `0` to `n-1`:\n   - Initialize a temporary list to store ancestors.\n   - Use a boolean array to keep track of visited nodes.\n   - Perform DFS from node `i` to find all ancestors and store them in the temporary list.\n4. **Sort and Store**: Sort the temporary list of ancestors and add it to the output list.\n\n\n## Time Complexity\n\n- **Graph Construction**: O(E), where `E` is the number of edges.\n- **DFS Traversal**: O(V + E) for each node, where `V` is the number of vertices.\n  - Since we perform DFS from each node, the total complexity becomes O(V * (V + E)).\n\nOverall, the time complexity is **O(V^2 + V*E)**.\n\n\n## Space Complexity\n\n- **Graph Storage**: O(V + E) for storing the adjacency list.\n- **DFS Storage**: O(V) for the visited array and recursion stack in the worst case.\n- **Output Storage**: O(V^2) for storing the list of lists.\n\nOverall, the space complexity is **O(V^2 + E)**.\n\n\n# Code\n```\nclass Solution {\n    private void dfs(List<List<Integer>> graph,int src,List<Integer> temp,boolean []vis){\n        vis[src]=true;\n        for(int i=0;i<graph.get(src).size();i++){\n            if(!vis[graph.get(src).get(i)]){\n            temp.add(graph.get(src).get(i));\n            dfs(graph,graph.get(src).get(i),temp,vis);\n            }\n        }\n    }\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<List<Integer>> graph=new ArrayList<>();\n        for(int i=0;i<n;i++){\n            graph.add(new ArrayList<>());\n        }\n        for(int i=0;i<edges.length;i++){\n            graph.get(edges[i][1]).add(edges[i][0]);\n        }\n        List<List<Integer>> output=new ArrayList<>();\n        for(int i=0;i<n;i++){\n            List<Integer> temp=new ArrayList<>();\n            boolean vis[]=new boolean[n];\n            dfs(graph,i,temp,vis);\n            Collections.sort(temp);\n            output.add(temp);\n        }\n        return output;\n    }\n}\n```
['Depth-First Search', 'Graph', 'Java']