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

Intuition

In a Directed Acyclic Graph (DAG), nodes have directed edges that indicate a relationship from one node to another. To find the ancestors of each node, we need to determine which nodes can reach a given node via directed paths. The problem requires identifying all such ancestors and returning them sorted.

Approach

1. Graph Representation: Use an adjacency list to represent the graph. Each node points to a set of nodes it can directly reach.
2. Depth-First Search (DFS): Implement a DFS function to explore each node and find all reachable nodes, marking them as ancestors. This involves recursively visiting nodes and adding the current node to the list of ancestors for each of its descendants.
3. Traversal and Collection: For each node, initiate a DFS. Use a visited array to avoid revisiting nodes within the same DFS call, preventing cycles and redundant work.
4. Sorting: After all ancestors are found for each node, sort the ancestor lists to meet the problem's requirement.

Complexity

• Time Complexity: O(n^2), where n is the number of nodes. Each node's DFS can visit all other nodes in the worst case.
• Space Complexity: O(n^2), required for the adjacency list, ancestor list, and visited array.

Detailed Explanation

var map = Array.from({ length: n }, () => new Set());
var res = Array.from({ length: n }, () => []);
var visited = new Uint8Array(n);

• map: An array of sets where each index corresponds to a node and contains a set of nodes it can directly reach.
• res: An array of arrays that will hold the list of ancestors for each node.
• visited: A boolean array used to keep track of visited nodes during DFS to avoid revisits.

var dfs = (v, p) => {
  visited[v] = 1;
  if (v !== p) res[v].push(p);
  for (var x of map[v]) if (!visited[x]) dfs(x, p);
};

• dfs: A depth-first search function that traverses the graph from node v, marking ancestors in res. If v is not the starting node p, p is added as an ancestor of v.

edges.forEach(([u, v]) => map[u].add(v));

• Populate the map with edges where each edge [u, v] indicates a direct connection from node u to node v.

for (let i = 0; i < n; ++i) visited.fill(0), dfs(i, i);

• For each node i, reset the visited array and perform a DFS starting from i. This finds all ancestors of i.

return res;

• Return the res array containing sorted lists of ancestors for each node.

Code

C++

class Solution {
public:
    vector> getAncestors(int n, vector>& edges) {
        vector> map(n);
        vector> res(n);
        vector visited(n);

        function dfs = [&](int v, int p) {
            visited[v] = true;
            if (v != p) res[v].push_back(p);
            for (int x : map[v]) {
                if (!visited[x]) dfs(x, p);
            }
        };

        for (const auto& edge : edges) {
            map[edge[0]].insert(edge[1]);
        }

        for (int i = 0; i < n; ++i) {
            fill(visited.begin(), visited.end(), false);
            dfs(i, i);
        }

        return res;
    }
};

Python

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

        def dfs(v: int, p: int):
            visited[v] = True
            if v != p:
                res[v].append(p)
            for x in map[v]:
                if not visited[x]:
                    dfs(x, p)

        for u, v in edges:
            map[u].add(v)

        for i in range(n):
            visited = [False] * n
            dfs(i, i)

        return res

Java

class Solution {
    public List> getAncestors(int n, int[][] edges) {
        List> map = new ArrayList<>();
        List> res = new ArrayList<>();
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            map.add(new HashSet<>());
            res.add(new ArrayList<>());
        }

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

        for (int i = 0; i < n; i++) {
            Arrays.fill(visited, false);
            dfs(i, i, map, res, visited);
        }

        return res;
    }

    private void dfs(int v, int p, List> map, List> res, boolean[] visited) {
        visited[v] = true;
        if (v != p) res.get(v).add(p);
        for (int x : map.get(v)) {
            if (!visited[x]) {
                dfs(x, p, map, res, visited);
            }
        }
    }
}

JavaScript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function (n, edges) {
    var map = Array.from({ length: n }, () => new Set());
    var res = Array.from({ length: n }, () => []);
    var visited = new Uint8Array(n);

    var dfs = (v, p) => {
        visited[v] = 1;
        if (v !== p) res[v].push(p);
        for (var x of map[v]) if (!visited[x]) dfs(x, p);
    };

    edges.forEach(([u, v]) => map[u].add(v));
    for (let i = 0; i < n; ++i) visited.fill(0), dfs(i, i);
    return res;
};