# All Ancestors of a Node in a Directed Acyclic Graph
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph)
Canonical: https://scaleengineer.com/dsa/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
**Companies:** [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
You are given a positive integer `n` representing the number of nodes of a **Directed Acyclic Graph** (DAG). The nodes are numbered from `0` to `n - 1` (**inclusive**).

You are also given a 2D integer array `edges`, where `edges[i] = [fromi, toi]` denotes that there is a **unidirectional** edge from `fromi` to `toi` in the graph.

Return _a list_ `answer`_, where_ `answer[i]` _is the **list of ancestors** of the_ `ith` _node, sorted in **ascending order**_.

A node `u` is an **ancestor** of another node `v` if `u` can reach `v` via a set of edges.

**Example 1:**

![](https://assets.glich.co/dsa/all-ancestors-of-a-node-in-a-directed-acyclic-graph/image0.png) 

**Input:** n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
**Output:** [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
**Explanation:**
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

**Example 2:**

![](https://assets.glich.co/dsa/all-ancestors-of-a-node-in-a-directed-acyclic-graph/image1.png) 

**Input:** n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
**Output:** [[],[0],[0,1],[0,1,2],[0,1,2,3]]
**Explanation:**
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

**Constraints:**

* `1 <= n <= 1000`
* `0 <= edges.length <= min(2000, n * (n - 1) / 2)`
* `edges[i].length == 2`
* `0 <= fromi, toi <= n - 1`
* `fromi != toi`
* There are no duplicate edges.
* The graph is **directed** and **acyclic**.

# Approaches
## Iterative Traversal on Reversed Graph
This approach finds ancestors for each node independently. For any given node `i`, its ancestors are all nodes from which `i` is reachable. This is equivalent to finding all nodes that are reachable *from* `i` in a graph where all edge directions are reversed. We can run a separate graph traversal (like BFS or DFS) for each node on this reversed graph.
**Time:** O(n * (n + m)), where n is the number of nodes and m is the number of edges. Building the reversed graph takes O(n + m). For each of the n nodes, we perform a traversal (BFS/DFS) which takes O(n + m) in the worst case. Sorting all ancestor lists takes an additional O(n^2 * log n) in the worst case, but this is dominated by the traversal complexity. · **Space:** O(n^2 + m). The reversed adjacency list takes O(n + m) space. The result list `ancestorsList` can store up to O(n^2) elements in total. The `visited` array and queue for BFS in each iteration take O(n) space.
**Pros:** Conceptually simple and straightforward to implement.; Correctly solves the problem and is efficient enough for the given constraints.
**Cons:** Inefficient due to redundant computations. The reachability from an ancestor `a` to a parent `p` of node `i` is re-calculated for every child of `p`.
### Explanation
To find the ancestors of a specific node, say `v`, we need to identify all nodes `u` such that there exists a path from `u` to `v`. A more direct way to frame this is to reverse all the edges of the graph. In this reversed graph, a path from `v` to `u` signifies that `u` is an ancestor of `v` in the original graph.
This method iterates through each node `i` from `0` to `n-1` and, for each one, performs a full graph traversal (BFS is used in the code below) starting from `i` on the reversed graph. All reachable nodes discovered during this traversal are the ancestors of `i`. After collecting all ancestors for a node, the list is sorted as required by the problem statement.
```java
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        // Build a reversed adjacency list
        List<List<Integer>> revAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            revAdj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            revAdj.get(edge[1]).add(edge[0]);
        }

        List<List<Integer>> ancestorsList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> currentAncestors = new ArrayList<>();
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            
            queue.add(i);
            visited[i] = true; // Mark start node as visited

            while (!queue.isEmpty()) {
                int u = queue.poll();
                // Add to ancestors list only if it's not the start node
                if (u != i) {
                    currentAncestors.add(u);
                }

                for (int v : revAdj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.add(v);
                    }
                }
            }
            Collections.sort(currentAncestors);
            ancestorsList.add(currentAncestors);
        }
        return ancestorsList;
    }
}
```
To make the code slightly cleaner, we can run the BFS and collect all visited nodes, then sort and add them. The logic of not adding the start node `i` to its own ancestor list can be handled by starting the traversal from its parents in the reversed graph, or by simply filtering it out from the result of a traversal starting at `i`.
The BFS for each node explores a part of the graph. Since this is done for every node, many paths might be traversed multiple times, leading to inefficiency.
### Algorithm
- 1. Construct the reversed graph. Create an adjacency list `reversedAdj` where if `u -> v` is an edge in the original graph, we add an edge `v -> u`.
- 2. Initialize a list of lists `ancestors` to store the results.
- 3. For each node `i` from `0` to `n-1`:
    - a. Perform a Breadth-First Search (BFS) starting from `i` on the `reversedAdj`.
    - b. Use a `visited` array to keep track of visited nodes to avoid redundant processing.
    - c. All nodes visited during this traversal are ancestors of `i`. Collect them.
    - d. Sort the collected ancestors for node `i` and add them to the final result list.

## Topological Sort with Ancestor Set Propagation
This approach leverages the Directed Acyclic Graph (DAG) property. We can process nodes in a topological order, which ensures that when we calculate the ancestors for a node `u`, the ancestors for all its predecessors (parents) have already been fully determined. This allows us to build the ancestor sets dynamically, avoiding redundant computations.
**Time:** O(n*m*log n) or O(n*m). Building graphs and topological sort takes O(n + m). The main work is propagating ancestor sets. For each edge p -> u, we perform a set union. The total work is `sum_{p->u} |ancestors(p)|`. With a `TreeSet`, this is `sum_{p->u} |ancestors(p)| * log(|ancestors(u)|)`. A loose upper bound is O(n*m*log n). If using `HashSet` and sorting at the end, it's closer to O(n*m + n^2*log n). Given the constraints (m <= 2000), this is generally faster than O(n*(n+m)). · **Space:** O(n^2 + m). The adjacency lists and in-degree array take O(n + m). The `ancestorSets` can store up to O(n^2) elements in total in the worst-case scenario (e.g., a complete DAG).
**Pros:** More efficient than the iterative traversal approach, especially for sparse graphs.; Avoids redundant computations by building upon previously computed results using dynamic programming.
**Cons:** More complex to implement, requiring topological sort and careful propagation of ancestor sets.; Space complexity can be high for dense graphs, although it's the same worst-case as the simpler approach.
### Explanation
The core idea is that the ancestors of a node `u` are the union of its direct parents and the ancestors of those parents.
`ancestors(u) = U_{p in parents(u)} ({p} U ancestors(p))`
By processing nodes in a topological order, we guarantee that by the time we process node `u`, the `ancestors(p)` for all its parents `p` are already computed.
We first perform a topological sort (Kahn's algorithm is a good choice) to establish the processing order. Then, we iterate through the topologically sorted nodes. For each node `u`, we look at its parents `p` (using a pre-built reversed graph). We then merge the parent `p` itself and all of `p`'s ancestors into `u`'s ancestor set. Using a `TreeSet` is convenient as it handles sorting and uniqueness automatically.
```java
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        List<List<Integer>> revAdj = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
            revAdj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            revAdj.get(edge[1]).add(edge[0]);
            inDegree[edge[1]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                q.add(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            topoOrder.add(u);
            for (int v : adj.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.add(v);
                }
            }
        }

        List<Set<Integer>> ancestorSets = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ancestorSets.add(new TreeSet<>()); // TreeSet to keep ancestors sorted
        }

        for (int u : topoOrder) {
            for (int p : revAdj.get(u)) {
                ancestorSets.get(u).add(p);
                ancestorSets.get(u).addAll(ancestorSets.get(p));
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            result.add(new ArrayList<>(ancestorSets.get(i)));
        }

        return result;
    }
}
```
This dynamic programming approach on the DAG is more efficient as it avoids the redundant computations of the simpler traversal-per-node method.
### Algorithm
- 1. Build both a standard adjacency list `adj` and a reversed adjacency list `revAdj`. Also, compute the in-degree of each node.
- 2. Perform a topological sort using Kahn's algorithm to get a valid processing order of nodes.
- 3. Initialize a list of sets, `ancestorSets`, to store ancestors for each node. Using a `TreeSet` automatically handles duplicates and keeps the elements sorted.
- 4. Iterate through the nodes `u` in the topological order:
    - a. For each direct parent `p` of `u` (found using `revAdj`):
    - b. Add `p` to the ancestor set of `u`.
    - c. Add all ancestors of `p` (from `ancestorSets.get(p)`) to the ancestor set of `u`.
- 5. Convert the `TreeSet`s to `ArrayList`s to match the required output format.

# Solutions
### CSharp

```csharp
public class Solution {
    private int n;
    private List < int > [] g;
    private IList < IList < int >> ans;
    public IList < IList < int >> GetAncestors(int n, int[][] edges) {
        g = new List < int > [n];
        this.n = n;
        for (int i = 0; i < n; i++) {
            g[i] = new List < int > ();
        }
        foreach(var e in edges) {
            g[e[0]].Add(e[1]);
        }
        ans = new List < IList < int >> ();
        for (int i = 0; i < n; ++i) {
            ans.Add(new List < int > ());
        }
        for (int i = 0; i < n; ++i) {
            BFS(i);
        }
        return ans;
    }
    private void BFS(int s) {
        Queue < int > q = new Queue < int > ();
        q.Enqueue(s);
        bool[] vis = new bool[n];
        vis[s] = true;
        while (q.Count > 0) {
            int i = q.Dequeue();
            foreach(int j in g[i]) {
                if (!vis[j]) {
                    vis[j] = true;
                    q.Enqueue(j);
                    ans[j].Add(s);
                }
            }
        }
    }
}
```

### Java

```java
class Solution { private int n ; private List < Integer >[] g ; private List < List < Integer >> ans ; public List < List < Integer >> getAncestors ( int n , int [][] edges ) { g = new List [ n ]; this . n = n ; Arrays . setAll ( g , i -> new ArrayList <>()); for ( var e : edges ) { g [ e [ 0 ]]. add ( e [ 1 ]); } ans = new ArrayList <>(); for ( int i = 0 ; i < n ; ++ i ) { ans . add ( new ArrayList <>()); } for ( int i = 0 ; i < n ; ++ i ) { bfs ( i ); } return ans ; } private void bfs ( int s ) { Deque < Integer > q = new ArrayDeque <>(); q . offer ( s ); boolean [] vis = new boolean [ n ]; vis [ s ] = true ; while (! q . isEmpty ()) { int i = q . poll (); for ( int j : g [ i ]) { if (! vis [ j ]) { vis [ j ] = true ; q . offer ( j ); ans . get ( j ). add ( s ); } } } } }
```

### CPP

```cpp
class Solution { public: vector < vector < int >> getAncestors ( int n , vector < vector < int >>& edges ) { vector < int > g [ n ]; for ( auto & e : edges ) { g [ e [ 0 ]]. push_back ( e [ 1 ]); } vector < vector < int >> ans ( n ); auto bfs = [ & ]( int s ) { queue < int > q ; q . push ( s ); bool vis [ n ]; memset ( vis , 0 , sizeof ( vis )); vis [ s ] = true ; while ( q . size ()) { int i = q . front (); q . pop (); for ( int j : g [ i ]) { if ( ! vis [ j ]) { vis [ j ] = true ; ans [ j ]. push_back ( s ); q . push ( j ); } } } }; for ( int i = 0 ; i < n ; ++ i ) { bfs ( i ); } return ans ; } };
```

### Python

```python
class Solution : def getAncestors ( self , n : int , edges : List [ List [ int ]]) -> List [ List [ int ]]: def bfs ( s : int ): q = deque ([ s ]) vis = { s } while q : i = q . popleft () for j in g [ i ]: if j not in vis : vis . add ( j ) q . append ( j ) ans [ j ]. append ( s ) g = defaultdict ( list ) for u , v in edges : g [ u ]. append ( v ) ans = [[] for _ in range ( n )] for i in range ( n ): bfs ( i ) return ans
```