# 2192. All Ancestors of a Node in a Directed Acyclic Graph
###### tags: `Leetcode` `Medium` `Topological Sort` `BFS`
Link: https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/
## 思路
### 思路一 Topological Sort $O(N^2logN)$ $O(N^2)$
和[1462. Course Schedule IV](https://hackmd.io/QrubTV-KT9CEUdjsdvd7lw)的思路有点像
都是找到每个node的ancestor
做法是先建graph 然后在bfs的同时存ancestor
由于输出的ancestor要按顺序 所以先用了treeset 之后再output到list里面
### 思路二 DFS $O(N^2)$ $O(N^2)$ (more efficient)
先建图 记录每个node的child
然后对于每一个node做dfs 找到它所有的child 并且在它的child的ancestor list上加上他自己
这样不用排序 就可以得到答案
但问题在于如果A->B B->C A->C的话那么A就会被加进C的ancestor list两次 所以需要加之前需要检验一下是不是已经访问过了
## Code
### 思路一 Topological Sort $O(N^2)$ $O(N^2)$

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        List<Set<Integer>> ancestor = new ArrayList<>();
        int[] ancestorNum = new int[n];
        
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
            ancestor.add(new TreeSet<>());
        }
        
        for(int[] edge:edges){
            int a = edge[0], b = edge[1];
            graph.get(a).add(b);
            ancestorNum[b]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<n; i++){
            if(ancestorNum[i]==0) q.add(i);
        }
        
        while(!q.isEmpty()){
            int curr = q.poll();
            for(int next:graph.get(curr)){
                ancestor.get(next).add(curr);
                ancestor.get(next).addAll(ancestor.get(curr));
                ancestorNum[next]--;
                if(ancestorNum[next]==0) q.add(next);
            }
        }
        
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0; i<n; i++){
            ans.add(new ArrayList<>(ancestor.get(i)));
        }
        return ans;
    }
}

### 思路二 DFS $O(N^2)$ $O(N^2)$ (more efficient)

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        ans = [[] for _ in range(n)]
        graph = [[] for _ in range(n)]
        visited = [False]*n
        for a, b in edges:
            graph[a].append(b)
        
        def dfs(start, curr):
            for nextNode in graph[curr]:
                if len(ans[nextNode])==0 or ans[nextNode][-1]!=start:
                    ans[nextNode].append(start)
                    dfs(start, nextNode)

        for i in range(n):
            dfs(i, i)
        
        return ans

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
            ans.add(new ArrayList<>());
        }
        for(int[] edge:edges){
            graph.get(edge[0]).add(edge[1]);
        }
        
        for(int i=0; i<n; i++){
            dfs(ans, graph, i, i);
        }
        return ans;
    }
    private void dfs(List<List<Integer>> ans, List<List<Integer>> graph, int curr, int anc){
        for(int next:graph.get(curr)){
            if(ans.get(next).size()==0 || ans.get(next).get(ans.get(next).size()-1)!=anc){
                ans.get(next).add(anc);
                dfs(ans, graph, next, anc);
            }
        }
    }
}