Skip to main content

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

Problem Description​

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.

Examples​

Example 1: image

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

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.

Solution for 2192. All Ancestors of a Node in a Directed Acyclic Graph​

1. Initialize Data Structures​

  • Create an adjacency list to represent the graph.
  • Create an answer list to store the ancestors for each node.

2. Build the Graph​

  • Populate the adjacency list from the given edges. Each edge [u, v] represents a directed edge from node u to node v.

3. Depth-First Search (DFS) Traversal​

  • For each node in the graph, perform a DFS to find all its ancestors.
  • Mark the current node as visited.
  • For each adjacent node that has not been visited, add the parent node to its ancestor list and continue the DFS traversal.

4. Return the Result​

  • After traversing all nodes, return the list of ancestors for each node.

Implementation​

Live Editor
function Solution(arr) {
  function  dfs(node, parent, ans, vis, adj) {
    vis[node] = 1;
    for (let adjNode of adj[node]) {
        if (!vis[adjNode]) {
            ans[adjNode].push(parent);
            dfs(adjNode, parent, ans, vis, adj);
        }
    }
}

function getAncestors(n, edges) {
    let ans = Array.from({ length: n }, () => []);
    let adj = Array.from({ length: n }, () => []);
    for (let [u, v] of edges) {
        adj[u].push(v);
    }

    for (let i = 0; i < n; i++) {
        let vis = new Array(n).fill(0);
        dfs(i, i, ans, vis, adj);
    }
    return ans;
}
  const input  = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
  const output = getAncestors(input, edgeList)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(N2+N∗E)O(N^2 + N*E)
  • Space Complexity: O(N2) O(N^2)

Code in Different Languages​

Written by @hiteshgahanolia
class Solution {
dfs(node, parent, ans, vis, adj) {
vis[node] = 1;
for (let adjNode of adj[node]) {
if (!vis[adjNode]) {
ans[adjNode].push(parent);
this.dfs(adjNode, parent, ans, vis, adj);
}
}
}

getAncestors(n, edges) {
let ans = Array.from({ length: n }, () => []);
let adj = Array.from({ length: n }, () => []);
for (let [u, v] of edges) {
adj[u].push(v);
}

for (let i = 0; i < n; i++) {
let vis = new Array(n).fill(0);
this.dfs(i, i, ans, vis, adj);
}
return ans;
}
}

References​