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

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:

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.

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<vector<int>> getAncestors(int numNodes, vector<vector<int>>& edges) {
        vector<vector<int>> ancestors(numNodes); // Stores the ancestors for each node
        vector<vector<int>> graph(numNodes);     // Adjacency list for the graph

        // Build the graph from edges
        for (const vector<int>& edge : edges) {
            const int fromNode = edge[0];
            const int toNode = edge[1];
            graph[fromNode].push_back(toNode);
        }

        // Perform DFS for each node to find all ancestors
        for (int currentNode = 0; currentNode < numNodes; ++currentNode) {
            vector<bool> visited(numNodes, false);
            dfs(graph, currentNode, currentNode, visited, ancestors);
        }

        return ancestors;
    }

private:
    void dfs(const vector<vector<int>>& graph, int currentNode, int ancestor, vector<bool>& visited, vector<vector<int>>& ancestors) {
        visited[currentNode] = true;
        for (const int neighbor : graph[currentNode]) {
            if (visited[neighbor])
                continue;
            ancestors[neighbor].push_back(ancestor);
            dfs(graph, neighbor, ancestor, visited, ancestors);
        }
    }
};

from typing import List

class Solution:
    def getAncestors(self, numNodes: int, edges: List[List[int]]) -> List[List[int]]:
        ancestors = [[] for _ in range(numNodes)]  # Stores the ancestors for each node
        graph = [[] for _ in range(numNodes)]      # Adjacency list for the graph

        # Build the graph from edges
        for edge in edges:
            fromNode, toNode = edge
            graph[fromNode].append(toNode)

        # Perform DFS for each node to find all ancestors
        for currentNode in range(numNodes):
            visited = [False] * numNodes
            self.dfs(graph, currentNode, currentNode, visited, ancestors)

        return ancestors

    def dfs(self, graph: List[List[int]], currentNode: int, ancestor: int, visited: List[bool], ancestors: List[List[int]]):
        visited[currentNode] = True
        for neighbor in graph[currentNode]:
            if visited[neighbor]:
                continue
            ancestors[neighbor].append(ancestor)
            self.dfs(graph, neighbor, ancestor, visited, ancestors)

Time Complexity

• Building the Graph: Building the adjacency list from the given edges.
  Time Complexity: \( O(E) \), where \( E \) is the number of edges.
• Performing DFS for Each Node: Running DFS from each node to find all ancestors.
  Time Complexity: \( O(V + E) \), where \( V \) is the number of nodes and \( E \) is the number of edges.
• Overall Time Complexity: \( O(V + E) \).

Space Complexity

• Storing the Ancestors: The space required for storing the ancestors of each node.
  Space Complexity: \( O(V^2) \).
• Graph Representation: The space used for the adjacency list.
  Space Complexity: \( O(V + E) \).
• DFS Call Stack and Visited Vector: The space for the DFS call stack and the visited vector.
  Space Complexity: \( O(V) \).
• Overall Space Complexity: \( O(V^2 + V + E) \approx O(V^2) \).