#2192

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

All Ancestors of a Node in a Directed Acyclic Graph

Solve the All Ancestors of a Node in a Directed Acyclic Graph problem using graph traversal techniques like BFS, DFS, and topological sort.

depth first search breadth first search graph topological sort

Problem Statement

Given a Directed Acyclic Graph (DAG) with n nodes, each numbered from 0 to n-1, and a list of directed edges, your task is to find all ancestors for each node. A directed edge [from, to] indicates a path from node 'from' to node 'to'.

Return a list of lists, where each list contains the ancestors of the corresponding node in sorted order. For each node i, you must determine all nodes that can reach i through a directed path.

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]]

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]]

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 Approach

Graph Construction and Reverse Traversal

You can represent the graph as an adjacency list, then reverse the graph's edges. This transformation allows you to traverse the graph backward, gathering ancestors for each node.

Topological Sorting with DFS

Perform a topological sort of the graph, processing each node in order. For each node, traverse its ancestors by traversing the reversed graph using DFS, collecting all reachable nodes as ancestors.

Efficient Graph Traversal with BFS

Alternatively, use BFS to traverse the reversed graph. For each node, start from that node and propagate the ancestors upwards, collecting all ancestors and ensuring they are processed in ascending order.

Complexity Analysis

Metric	Value
Time	O(n^2 + m)
Space	O(n^2 + m)

The time complexity is O(n^2 + m) due to the graph traversal steps (where n is the number of nodes and m is the number of edges). The space complexity is O(n^2 + m) as well, considering the storage for graph representation and traversal.

What Interviewers Usually Probe

Ability to apply reverse graph traversal to collect ancestors.
Understanding of topological sorting and how it aids in graph processing.
Knowledge of BFS/DFS and their application in DAGs.

Common Pitfalls or Variants

Common pitfalls

Failing to reverse the graph before starting ancestor collection.
Not handling edge cases where nodes have no ancestors.
Inefficient traversal that leads to redundant computations for each node.

Follow-up variants

Consider how reversing the graph affects traversal and memory use.
Explore the trade-offs between DFS and BFS for this problem.
Test performance on larger graphs with up to 1000 nodes and 2000 edges.

FAQ

What is the best way to find ancestors in a DAG?

Reversing the graph and using topological sorting allows you to efficiently find ancestors using DFS or BFS.

How can I optimize the space complexity of this problem?

You can reduce space usage by only storing the necessary traversal data and using in-place modifications for graph traversal.

Why should I reverse the edges in this problem?

Reversing the edges makes it easier to traverse backward from each node, collecting ancestors efficiently.

What are the main challenges in this problem?

The main challenges include efficiently traversing the graph, handling large input sizes, and ensuring no redundant processing of nodes.

How do I use topological sorting in this problem?

Topological sorting orders the nodes in a way that makes it easy to process ancestors. By sorting the nodes before traversal, you ensure that all ancestors of a node are processed before the node itself.

terminal

Solution

Solution 1: BFS

First, we construct the adjacency list $g$ based on the two-dimensional array $edges$, where $g[i]$ represents all successor nodes of node $i$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        def bfs(s: int):
            q = deque([s])
            vis = {s}
            while q:
                i = q.popleft()
                for j in g[i]:
                    if j not in vis:
                        vis.add(j)
                        q.append(j)
                        ans[j].append(s)

        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
        ans = [[] for _ in range(n)]
        for i in range(n):
            bfs(i)
        return ans

Continue Practicing

#2328 number of increasing paths in a grid #2360 longest cycle in a graph #1462 course schedule iv