Finding All Ancestors of Nodes in a Directed Acyclic Graph (DAG) Using BFS
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find the ancestors of each node in a Directed Acyclic Graph (DAG), the idea is to tr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find the ancestors of each node in a Directed Acyclic Graph (DAG), the idea is to traverse the graph and track the reachability of nodes. For each node, if it can be reached from another node, then that other node is its ancestor.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Graph Representation: Use an adjacency list to represent the graph. This allows efficient traversal of the nodes.\n2. Initialization: Create an empty list of lists to store the ancestors for each node.\n3. BFS Traversal: For each node, perform a Breadth-First Search (BFS) to find all reachable nodes. During BFS, if a node j is reachable from node i, then i is an ancestor of j. Add i to the ancestor list of j.\n4. Sorting: Since the ancestors need to be in ascending order, the BFS naturally processes nodes in ascending order.\n# Complexity\n- Time complexity: O(n+e) where n is the number of nodes and e is the number of edges\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The overall space complexity is O(n+e)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    private int n;\n    private List<Integer>[] g;\n    private List<List<Integer>> ans;\n\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        g = new List[n];\n        this.n = n;\n        Arrays.setAll(g, i -> new ArrayList<>());\n        for (var e : edges) {\n            g[e[0]].add(e[1]);\n        }\n        ans = new ArrayList<>();\n        for (int i = 0; i < n; ++i) {\n            ans.add(new ArrayList<>());\n        }\n        for (int i = 0; i < n; ++i) {\n            bfs(i);\n        }\n        return ans;\n    }\n\n    private void bfs(int s) {\n        Deque<Integer> q = new ArrayDeque<>();\n        q.offer(s);\n        boolean[] vis = new boolean[n];\n        vis[s] = true;\n        while (!q.isEmpty()) {\n            int i = q.poll();\n            for (int j : g[i]) {\n                if (!vis[j]) {\n                    vis[j] = true;\n                    q.offer(j);\n                    ans.get(j).add(s);\n                }\n            }\n        }\n    }\n}\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'C++', 'Java']