Java Intuitive and easy solution
Intuition\nTo solve this problem, we will use Depth-First Search (DFS) to find all ancestors for each node in the graph. Here are the steps we will follow:\n\n1
# Intuition\nTo solve this problem, we will use Depth-First Search (DFS) to find all ancestors for each node in the graph. Here are the steps we will follow:\n\n1. Construct the Graph: We will first construct the graph as an adjacency list, but we will reverse the direction of edges. This way, for any node v, graph[v] will contain all nodes u such that there is an edge from u to v.\n\n2. Depth-First Search (DFS): For each node, we will perform a DFS to find all its ancestors. We will keep track of visited nodes to avoid cycles and duplicate ancestors.\n\n3. Sort and Collect Results: After performing DFS for each node, we will sort the list of ancestors and add it to the final result.\n\n# Approach\n1. Graph Construction: Initialize an adjacency list graph where graph[i] is a list of nodes that have a direct edge to i. Iterate through the edges array and populate the adjacency list with reversed edges.\n\n2. DFS Traversal: For each node from 0 to n-1, perform a DFS to find all ancestors:\n\n- Create a vis array to keep track of visited nodes during the DFS.\n- Create a temp list to store ancestors for the current node.\n- Use the dfs function to recursively visit all ancestors, marking nodes as visited and adding them to the temp list.\n3. Sort and Collect Results: After the DFS traversal for each node, sort the temp list to ensure ancestors are in ascending order, and add the sorted list to the final result ans.\n\n# Complexity\n- Time complexity:\nTime complexity is O(n\u22C5(n+m)), where n is the number of nodes and m is the number of edges. This is because for each node, we potentially traverse all other nodes and edges in the graph.\n\n- Space complexity:\nThe space complexity is O(n^2) for storing the graph and the result, as well as the space used by the DFS recursion stack.\n\n# Code\n```\nclass Solution {\n    public void dfs( List<Integer>[] graph , int curr , boolean vis[] ,List<Integer> temp ){\n        vis[curr] = true;\n\n        for(int i = 0 ; i < graph[curr].size() ; i++){\n            int neigh = graph[curr].get(i);\n           \n            if(!vis[neigh]){\n                temp.add(neigh);\n                dfs(graph, neigh , vis, temp);\n            }\n        }\n    }\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<Integer>[] graph = new ArrayList[n];\n        for (int i = 0; i < n; i++) {\n            graph[i] = new ArrayList<>();\n        }\n        \n        for (int i = 0; i < edges.length; i++) {\n            int u = edges[i][0];\n            int v = edges[i][1];\n            //reversing the array\n            graph[v].add(u);\n        }\n        \n        List<List<Integer>> ans =new ArrayList<>();\n        for(int i = 0;  i < n ; i++){\n            boolean vis[] = new boolean[n];\n            List<Integer> temp = new ArrayList<>();\n            dfs(graph , i , vis, temp);\n            Collections.sort(temp);\n            ans.add(temp);\n        }\n\n        return ans;\n        \n\n    }\n}\n```
['Depth-First Search', 'Graph', 'Java']