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:

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:

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.

Solution

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(N^2 + N*E)$
• Space Complexity: $O(N^2)$

Code in Different Languages

JavaScript

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;
 }
}

TypeScript

Written by @hiteshgahanolia

class Solution {
 dfs(node: number, parent: number, ans: number[][], vis: number[], adj: number[][]): void {
     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: number, edges: number[][]): number[][] {
     let ans = Array.from({ length: n }, () => []);
     let adj: number[][] = Array.from({ length: n }, () => []);
     for (let [u, v] of edges) {
         adj[u].push(v);
     }

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

Python

Written by @hiteshgahanolia

class Solution:
 def dfs(self, node, parent, ans, vis, adj):
     vis[node] = 1
     for adjNode in adj[node]:
         if not vis[adjNode]:
             ans[adjNode].append(parent)
             self.dfs(adjNode, parent, ans, vis, adj)

 def getAncestors(self, n, edges):
     ans = [[] for _ in range(n)]
     adj = [[] for _ in range(n)]
     for u, v in edges:
         adj[u].append(v)

     for i in range(n):
         vis = [0] * n
         self.dfs(i, i, ans, vis, adj)
     return ans

Java

Written by @hiteshgahanolia

import java.util.*;

class Solution {
 void dfs(int node, int parent, List<List<Integer>> ans, boolean[] vis, List<Integer>[] adj) {
     vis[node] = true;
     for (int adjNode : adj[node]) {
         if (!vis[adjNode]) {
             ans.get(adjNode).add(parent);
             dfs(adjNode, parent, ans, vis, adj);
         }
     }
 }

 public List<List<Integer>> getAncestors(int n, int[][] edges) {
     List<List<Integer>> ans = new ArrayList<>();
     for (int i = 0; i < n; i++) {
         ans.add(new ArrayList<>());
     }
     
     List<Integer>[] adj = new ArrayList[n];
     for (int i = 0; i < n; i++) {
         adj[i] = new ArrayList<>();
     }
     
     for (int[] edge : edges) {
         adj[edge[0]].add(edge[1]);
     }

     for (int i = 0; i < n; i++) {
         boolean[] vis = new boolean[n];
         dfs(i, i, ans, vis, adj);
     }
     return ans;
 }
}

C++

Written by @hiteshgahanolia

class Solution {
public:
 void dfs(int node ,int parent ,vector<vector<int>>&ans, vector<int>&vis , vector<int>adj[])
 {
     vis[node]=1;
     for(auto adjNode : adj[node])
     {
         if(!vis[adjNode])
         {
             ans[adjNode].push_back(parent);
             dfs(adjNode ,parent ,ans , vis , adj);
         }
     }

 }
 vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
     vector<vector<int>>ans(n);
     vector<int>adj[n];
     for(auto i:edges)
     {
         adj[i[0]].push_back(i[1]);
     }

     for(int i=0;i<n;i++)
     {
         vector<int>vis(n,0);
         dfs(i,i, ans , vis , adj);
     }
     return ans;
 }
};

References

• LeetCode Problem: 2192. All Ancestors of a Node in a Directed Acyclic Graph

• Solution Link: LeetCode Solution