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

### [Problem link](https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/)

###### tags: `leedcode` `medium` `c++` `DFS`

You are given a positive integer <code>n</code> representing the number of nodes of a **Directed Acyclic Graph** (DAG). The nodes are numbered from <code>0</code> to <code>n - 1</code> ( **inclusive** ).

You are also given a 2D integer array <code>edges</code>, where <code>edges[i] = [from_i, to_i]</code> denotes that there is a **unidirectional** edge from <code>from_i</code> to <code>to_i</code> in the graph.

Return a list <code>answer</code>, where <code>answer[i]</code> is the **list of ancestors** of the <code>i^th</code> node, sorted in **ascending order** .

A node <code>u</code> is an **ancestor** of another node <code>v</code> if <code>u</code> can reach <code>v</code> via a set of edges.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2019/12/12/e1.png" style="width: 322px; height: 265px;" />

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:**
<img alt="" src="https://assets.leetcode.com/uploads/2019/12/12/e2.png" style="width: 343px; height: 299px;" />

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:**

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

## Solution 1 - DFS
#### C++

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> grid(n);
        for (auto &edge: edges) {
            grid[edge[0]].push_back(edge[1]);
        }

        vector<vector<int>> ans(n);
        vector<int> seen(n, -1);
        int start = 0;

        function<void(int)> dfs = [&](int i) {
            seen[i] = start;
            for (int e: grid[i]) {
                if (seen[e] != start) {
                    ans[e].push_back(start);
                    dfs(e);
                }
            }
        };
        for (start = 0; start < n; start++) {
            dfs(start);
        }
        return ans;
    }
};

#### C++

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);

        for (vector<int>& edge: edges) {
            graph[edge[1]].push_back(edge[0]);  // child: parents
        }

        vector<vector<int>> ans(n);
        for (int i = 0; i < n; i++) {
            vector<int> seen(n, false);
            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                for (int& parent: graph[node]) {
                    if (seen[parent] == false) {
                        seen[parent] = true;
                        q.push(parent);
                    }
                }
            }
            for (int j = 0; j < seen.size(); j++) {
                if (seen[j]) {
                    ans[i].push_back(j);
                }
            }
        }
        return ans;
    }
};

>### Complexity
>m = edges.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n(n + m)) | O(n + m) |
>| Solution 1 | O(n(n + m)) | O(n + m) |

## Note
x