_2192. All Ancestors of a Node in a Directed Acyclic Graph.md

2192. All Ancestors of a Node in a Directed Acyclic Graph

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 29, 2024

Last updated : June 29, 2024

---

Related Topics : Depth-First Search, Breadth-First Search, Graph, Topological Sort

Acceptance Rate : 62.15 %

---

Solutions

• m2192 Daily.py
• m2192.java

Python

m2192 Daily.py

# We can basically do levelorder traversals starting at 0, 1, 2,...
# with compensating recursive calls

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        directAncestors = [set() for _ in range(n)]
        visited = [False] * n

        # Add immediate predecessors
        for source, target in edges :
            directAncestors[target].add(source)


        # Helper method that merges a node's ancestor set with 
        # any ancestor's ancestor set
        def helper(currentIndx: int) -> None :
            if visited[currentIndx] :
                return

            visited[currentIndx] = True
            if not directAncestors[currentIndx] : # is oldest ancestor
                return
            
            mergeSet = set()
            for item in directAncestors[currentIndx] :
                helper(item) # make sure it's been initialized first
                mergeSet |= directAncestors[item]
            
            directAncestors[currentIndx] |= mergeSet

        for i in range(n) :
            if not visited[i] :
                helper(i)
            

        return [sorted(list(x)) for x in directAncestors]

Java

m2192.java

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        ArrayList<HashSet<Integer>> parents = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            parents.add(new HashSet<Integer>());
        }

        boolean[] visited = new boolean[n];

        for (int[] edge : edges) {
            parents.get(edge[1]).add(edge[0]);
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                helper(i, visited, parents);
            }
        }

        List<List<Integer>> output = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            output.add(new ArrayList<Integer>());
            output.get(i).addAll(parents.get(i));
            Collections.sort(output.get(i));
        }

        return output;

    }
    
    private void helper(int currentIndx, boolean[] visited, ArrayList<HashSet<Integer>> parents) {
        if (visited[currentIndx]) {
            return;
        }

        visited[currentIndx] = true;
        if (parents.get(currentIndx).size() == 0) {
            return;
        }

        HashSet<Integer> mergeValues = new HashSet<>();
        for (Integer i : parents.get(currentIndx)) {
            helper(i, visited, parents);
            mergeValues.addAll(parents.get(i));
        }
        parents.get(currentIndx).addAll(mergeValues);
     }

}