[JAVA] Reverse the Graph!
Explanation\n\nIn this approach, we reverse the graph where direction between two node pairs are reversed. Originally if 3 was directing towards 4 then we build
**Explanation**\n\nIn this approach, we reverse the graph where direction between two node pairs are reversed. Originally if 3 was directing towards 4 then we build a graph where 4 will be directing towards 3. And the same goes for each and every node pair. Now all our ancestors turn into descendants who can be easily recovered using simple Depth First Search.\n\n**Time complexity :**   O(n^2 log n)\n\n```\nclass Solution {\n    \n    List<List<Integer>> output = new ArrayList<>();\n    \n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        \n        List<Integer> [] graph = new ArrayList[n];\n        \n        for(int i=0;i<n;++i) {\n            \n            graph[i] = new ArrayList<>();\n        }\n        \n        for(int [] edge : edges) {\n        \n            graph[edge[1]].add(edge[0]);\n        }\n        \n        for(int i=0;i<n;++i) {\n            \n            List<Integer> ans = new ArrayList<>();\n            \n            dfs(graph,i,new boolean[n],ans);\n            \n            Collections.sort(ans);  \n            output.add(ans);\n        }\n        \n        return output;\n    }\n       \n    public void dfs(List<Integer> [] graph, int vertex, boolean [] visit, List<Integer> ans) {\n        \n        for(int curr : graph[vertex]) {\n            \n            if(visit[curr]) continue;\n            \n            ans.add(curr);\n            visit[curr] = true;\n            dfs(graph,curr,visit,ans);\n        }\n    }\n}\n```
[]