Topological, DFS, easy and commented, with dry run explanation
Approach:\n\t1. \tIn this apprach,we will not update answer list while doing DFS at each node (this approach was taking more time and hence threw TLE).\n\t2. \t
## Approach:\n\t1. \tIn this apprach,we will not update answer list while doing DFS at each node (this approach was taking more time and hence threw TLE).\n\t2. \tIn this approach, we will instead iterate over all nodes. In each iteration, we will update that node as ancestor to all of the nodes it is connected directly or indirectly (via DFS).\n\t3. \tSee below dry-run to understand the approach more easily.  \n\n## Dry Run\n\tIt was bit hard to draw everything in the limited space, but did my best. Let me know if anything is unclear or need any explanation. \n\tJust follow the steps from a) to y) \n![image](https://assets.leetcode.com/users/images/c7fc01e3-5893-49de-83aa-672e4bce707e_1648155240.6652746.png)\n![image](https://assets.leetcode.com/users/images/acc5bf7a-065c-491a-b775-a6fab62fe86b_1648155335.1324124.png)\n\n**Zoomed bottom portion**\n![image](https://assets.leetcode.com/users/images/8626bd6f-1337-4ee6-aa46-34a1d5f40c2e_1648155407.7836995.png)\n\n\n\n\n\n\tBelow is how the answer will keep getting updated in each iteration:\n\t--------------------\n\ti: 0 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0]\n\t4, [0]\n\t5, [0]\n\t6, [0]\n\t7, [0]\n\t--------------------\n\ti: 1 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0]\n\t5, [0, 1]\n\t6, [0, 1]\n\t7, [0, 1]\n\t--------------------\n\ti: 2 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0, 2]\n\t5, [0, 1]\n\t6, [0, 1, 2]\n\t7, [0, 1, 2]\n\t--------------------\n\ti: 3 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0, 2]\n\t5, [0, 1, 3]\n\t6, [0, 1, 2, 3]\n\t7, [0, 1, 2, 3]\n\t--------------------\n\ti: 4 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0, 2]\n\t5, [0, 1, 3]\n\t6, [0, 1, 2, 3, 4]\n\t7, [0, 1, 2, 3]\n\t--------------------\n\ti: 5 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0, 2]\n\t5, [0, 1, 3]\n\t6, [0, 1, 2, 3, 4]\n\t7, [0, 1, 2, 3]\n\t--------------------\n\ti: 6 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0, 2]\n\t5, [0, 1, 3]\n\t6, [0, 1, 2, 3, 4]\n\t7, [0, 1, 2, 3]\n\t--------------------\n\ti: 7 , answer now: \n\t0, []\n\t1, []\n\t2, []\n\t3, [0, 1]\n\t4, [0, 2]\n\t5, [0, 1, 3]\n\t6, [0, 1, 2, 3, 4]\n\t7, [0, 1, 2, 3]\n\n\n\n## Code\n\n\tclass Solution {\n\t\tpublic List<List<Integer>> getAncestors(int n, int[][] edges) {\n\t\t\tList<List<Integer>> adjList = new ArrayList<>();                                  \n\t\t\tList<List<Integer>> answer  = new ArrayList<>();                                   \n\n\t\t\tinitialize(answer, adjList, n);                                                    // initialize answer and adjList lists with empty list. \n\t\t\tfillAdjList(adjList, edges, n);                                                    // fill adjacency list\n\t\t\tfor(int i = 0; i < n; i++){\n\t\t\t\tint ancestor = i;\n\t\t\t\tdfs(ancestor, i, adjList, answer);                                            // call DFS\n\t\t\t}\n\t\t\treturn answer;\n\t\t}    \n\n\t\tpublic void dfs(int ancestor, int src, List<List<Integer>> adjList, List<List<Integer>> answer){                // DFS method\n\t\t\tList<Integer> ancestorList = answer.get(src);\n\t\t\tif(ancestorList.isEmpty() || ancestorList.get( ancestorList.size() -1 ) != ancestor){         \n\t\t\t\tif(ancestor != src){ ancestorList.add(ancestor); }                           // add ancestor to ancestor list, if only ancestor list is either empty, or does not already contain ancestor node.\n\t\t\t\tfor(int dest : adjList.get(src)){\n\t\t\t\t\tdfs(ancestor, dest, adjList, answer);                                    // for each connected edge, do DFS recursion\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\tpublic void initialize(List<List<Integer>> answer, List<List<Integer>> adjList, int n){\n\t\t\tfor(int i = 0; i < n; i++){\n\t\t\t\tanswer.add(new ArrayList<>());\n\t\t\t\tadjList.add(new ArrayList<>());\n\t\t\t}\n\t\t}\n\n\t\tpublic void fillAdjList(List<List<Integer>> adjList, int[][] edges, int n){\n\t\t\tfor(int[] edge : edges){\n\t\t\t\tadjList.get(edge[0]).add(edge[1]);    \n\t\t\t}\n\t\t}\n\t}
['Depth-First Search', 'Topological Sort', 'Java']