How do you solve All Ancestors of a Node in a Directed Acyclic Graph on LeetCode?

All Ancestors of a Node in a Directed Acyclic Graph (LeetCode #2192) can be solved using Brute Force. The optimal approach is Brute Force with undefined time complexity and undefined space complexity. Key insight: In the brute force approach, we will check each node and perform a depth-first search (DFS) to find all reachable nodes (ancestors) for that node. This is straightforward but inefficient as it redundantly explores paths multiple times.

What is the time complexity of All Ancestors of a Node in a Directed Acyclic Graph?

The optimal solution for All Ancestors of a Node in a Directed Acyclic Graph runs in undefined time and uses undefined space. undefined

What algorithm or data structure is used to solve All Ancestors of a Node in a Directed Acyclic Graph?

All Ancestors of a Node in a Directed Acyclic Graph uses the following concepts: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort. The recommended patterns to study are: .

#2192

All Ancestors of a Node in a Directed Acyclic Graph

Medium

Depth-First SearchBreadth-First SearchGraph TheoryTopological Sort

LeetCode ↗

Approaches

💡

Intuition

Time Space

In the brute force approach, we will check each node and perform a depth-first search (DFS) to find all reachable nodes (ancestors) for that node. This is straightforward but inefficient as it redundantly explores paths multiple times.

⚙️

Algorithm

3 steps

1Step 1: Initialize an empty list of ancestors for each node.
2Step 2: For each node, perform a DFS to find all reachable nodes and store them as ancestors.
3Step 3: Sort the ancestors list for each node before returning.

solution.py23 lines

1# Full working Python code
2from collections import defaultdict
3
4def findAncestors(n, edges):
5    graph = defaultdict(list)
6    for u, v in edges:
7        graph[v].append(u)  # Reverse the graph
8    ancestors = [[] for _ in range(n)]
9
10    def dfs(node, visited, current):
11        for ancestor in graph[node]:
12            if ancestor not in visited:
13                visited.add(ancestor)
14                current.append(ancestor)
15                dfs(ancestor, visited, current)
16
17    for i in range(n):
18        visited = set()
19        current = []
20        dfs(i, visited, current)
21        ancestors[i] = sorted(current)
22
23    return ancestors

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.