Problem Description

You have a Directed Acyclic Graph (DAG) with n nodes, numbered from 0 to n - 1. The graph is defined by a list of directed edges, where each edge [from_i, to_i] represents a one-way connection from node from_i to node to_i.

Your task is to find all ancestors for each node in the graph. A node u is considered an ancestor of node v if there exists a path from u to v through the directed edges.

For each node i (from 0 to n - 1), you need to return a list of all its ancestors sorted in ascending order.

Example Understanding:

• If there's an edge from node 1 to node 2, then node 1 is an ancestor of node 2
• If there's a path from node 1 → node 2 → node 3, then both nodes 1 and 2 are ancestors of node 3
• Each node's ancestor list should be sorted in ascending order
• A node cannot be its own ancestor

The solution uses BFS to explore the graph. For each node i, it performs a BFS traversal to find all nodes reachable from i. For each reachable node j, node i is added to j's ancestor list. By processing nodes in ascending order (0 to n-1), and since each node only adds itself to its descendants' lists once, the final ancestor lists are automatically sorted.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have a Directed Acyclic Graph (DAG) with nodes and edges.

Is it a tree?

• No: While it's a DAG, it's not necessarily a tree. A tree has exactly one path between any two nodes and n-1 edges for n nodes. Our DAG can have multiple paths to a node and varying numbers of edges.

Is the problem related to directed acyclic graphs?

• Yes: The problem specifically mentions we're working with a DAG, and we need to find ancestors (which requires understanding the directed nature of edges).

Topological Sort

• While topological sort could be related to DAG problems, this specific problem is about finding ancestors (reachability), not ordering nodes based on dependencies.

However, the solution actually uses BFS rather than DFS. But if we were to use DFS, we could:

1. Start from each node and perform DFS to find all reachable nodes
2. For each reachable node, mark the starting node as its ancestor

The problem involves exploring graph connectivity (which nodes can reach which other nodes), making both DFS and BFS valid approaches. The given solution uses BFS for its iterative nature and ease of implementation, but DFS would work equally well by recursively exploring all paths from each node and recording ancestry relationships.

Conclusion: While the flowchart suggests Topological Sort for DAG problems, this particular problem is about reachability/connectivity in a DAG, which can be solved using either DFS or BFS traversal patterns. The solution chooses BFS, but DFS would follow a similar pattern of exploring from each node to find all its descendants.

Intuition

The key insight is to reverse our thinking about the ancestor relationship. Instead of trying to find all ancestors for each node directly, we can flip the perspective: for each node, find all nodes it can reach (its descendants), and then mark ourselves as an ancestor of those descendants.

Think of it this way: if node A can reach node B through some path, then A is an ancestor of B. So rather than asking "who are my ancestors?", we ask "who are my descendants?" and then tell each descendant "I am your ancestor."

Why does this work better? Because in a directed graph, it's straightforward to traverse forward along the edges to find reachable nodes. Starting from node i, we can easily explore all nodes reachable from i using standard graph traversal (BFS or DFS). For each reachable node j, we know that i is an ancestor of j.

The clever part is processing nodes in ascending order (0 to n-1). This ensures that when we add ancestors to each node's list, they're naturally added in sorted order. Node 0 will add itself to its descendants' lists first, then node 1, and so on.

The algorithm essentially answers the question: "If I start from node i, which nodes can I reach?" For every node j that i can reach, we record that i is an ancestor of j. By repeating this process for all nodes, we build up the complete ancestor lists.

This approach transforms a potentially complex problem of tracing backwards through the graph (finding ancestors) into a simpler problem of tracing forwards (finding descendants), which aligns naturally with how directed edges work.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

Solution Approach

The implementation uses BFS to systematically find all descendants of each node and record the ancestor relationships.

Data Structures Used:

1. Adjacency List (g): A defaultdict(list) where g[u] contains all direct successors of node u. This is built from the edges array to enable efficient graph traversal.
2. Answer Array (ans): A list of lists where ans[i] will store all ancestors of node i in ascending order.
3. Queue (q): A deque for BFS traversal to explore nodes level by level.
4. Visited Set (vis): Tracks which nodes have been visited during each BFS to avoid cycles and redundant processing.

Algorithm Steps:

1. Build the Graph: Convert the edge list into an adjacency list representation. For each edge [u, v], add v to the list of successors of u.

2. BFS from Each Node: For each node i from 0 to n-1:

   • Initialize BFS with node i as the starting point
   • Mark i as visited to avoid revisiting
   • While the queue is not empty:
     • Dequeue a node
     • For each successor j of the current node:
       • If j hasn't been visited in this BFS:
         • Mark j as visited
         • Add j to the queue for further exploration
         • Key step: Add i (the starting node) to ans[j] as an ancestor

3. Return Results: After processing all nodes, ans[i] contains all ancestors of node i in ascending order (guaranteed by processing nodes 0 to n-1 sequentially).

Why This Works:

• By starting BFS from node i, we find all nodes reachable from i
• For each reachable node j, we know i is an ancestor of j
• Processing nodes in ascending order (0, 1, 2, ..., n-1) ensures ancestors are added to each list in sorted order
• The visited set prevents infinite loops and ensures each node is processed only once per BFS

Time Complexity: O(n * (n + m)) where n is the number of nodes and m is the number of edges. We perform BFS from each of the n nodes, and each BFS can visit up to n nodes and traverse up to m edges.

Space Complexity: O(n * n) in the worst case for storing the answer, plus O(n + m) for the graph representation.

Example Walkthrough

Let's walk through a small example with 4 nodes and edges: [[0,1], [0,2], [1,3], [2,3]]

This creates the following DAG:

    0
   / \
  1   2
   \ /
    3

Step 1: Build the adjacency list

• g[0] = [1, 2] (node 0 points to nodes 1 and 2)
• g[1] = [3] (node 1 points to node 3)
• g[2] = [3] (node 2 points to node 3)
• g[3] = [] (node 3 has no outgoing edges)

Step 2: Initialize answer array

• ans = [[], [], [], []] (empty ancestor lists for each node)

Step 3: Process each node with BFS

Starting from node 0:

• Queue: [0], Visited: {0}
• Process node 0: successors are [1, 2]
  • Visit node 1: Add 0 to ans[1], Queue: [1], Visited: {0, 1}
  • Visit node 2: Add 0 to ans[2], Queue: [1, 2], Visited: {0, 1, 2}
• Process node 1: successor is [3]
  • Visit node 3: Add 0 to ans[3], Queue: [2, 3], Visited: {0, 1, 2, 3}
• Process node 2: successor is [3] (already visited, skip)
• Process node 3: no successors
• Result: ans = [[], [0], [0], [0]]

Starting from node 1:

• Queue: [1], Visited: {1}
• Process node 1: successor is [3]
  • Visit node 3: Add 1 to ans[3], Queue: [3], Visited: {1, 3}
• Process node 3: no successors
• Result: ans = [[], [0], [0], [0, 1]]

Starting from node 2:

• Queue: [2], Visited: {2}
• Process node 2: successor is [3]
  • Visit node 3: Add 2 to ans[3], Queue: [3], Visited: {2, 3}
• Process node 3: no successors
• Result: ans = [[], [0], [0], [0, 1, 2]]

Starting from node 3:

• Queue: [3], Visited: {3}
• Process node 3: no successors (no nodes reachable)
• Result: ans = [[], [0], [0], [0, 1, 2]]

Final Answer:

• Node 0: [] (no ancestors)
• Node 1: [0] (ancestor: 0)
• Node 2: [0] (ancestor: 0)
• Node 3: [0, 1, 2] (ancestors: 0, 1, 2)

Notice how the ancestors are automatically sorted because we processed nodes in order 0→1→2→3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 + n*m) which simplifies to O(n^2) in the worst case.

The algorithm performs a BFS starting from each of the n nodes. For each BFS:

• In the worst case, we visit all n nodes (when the graph is fully connected)
• For each visited node, we explore all its outgoing edges
• Each node is added to the ancestor list of its descendants once per source node

Since we run BFS n times and each BFS can visit up to n nodes while traversing up to m edges total, the time complexity is O(n * (n + m)). In the worst case where m = O(n^2) (complete graph), this becomes O(n^2).

Space Complexity: O(n^2)

The space complexity consists of:

• Graph adjacency list g: O(n + m) to store all edges
• Answer array ans: O(n^2) in the worst case, where each node could be an ancestor of every other node
• BFS queue q: O(n) at most
• Visited set vis: O(n) for each BFS call

The dominant factor is the answer array which can store up to n * (n-1) ancestor relationships, resulting in O(n^2) space complexity overall.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Maintaining Sorted Order of Ancestors

The Pitfall: A common mistake is attempting to optimize by processing nodes in a different order or adding ancestors as they're discovered during a reverse traversal. This can lead to unsorted ancestor lists.

Example of Incorrect Approach:

# WRONG: Processing edges directly without considering node order
for from_node, to_node in edges:
    # This might add ancestors out of order
    ancestors[to_node].append(from_node)

Why It Happens:

• Edges in the input aren't guaranteed to be in any particular order
• If node 5 has an edge to node 3, and later node 1 has an edge to node 3, the ancestors of node 3 would be [5, 1] instead of [1, 5]

The Solution: Always process nodes in ascending order (0 to n-1) and perform BFS from each node. This ensures ancestors are naturally added in sorted order:

# CORRECT: Process nodes in order
for node in range(n):  # 0, 1, 2, ..., n-1
    bfs(node)

2. Using Global Visited Set Across Multiple BFS Calls

The Pitfall: Reusing the same visited set for all BFS traversals, which prevents finding all ancestors.

Example of Incorrect Code:

# WRONG: Global visited set
visited = set()  # Shared across all BFS calls

def bfs(start_node):
    queue = deque([start_node])
    visited.add(start_node)  # This persists across calls!
  
    while queue:
        current = queue.popleft()
        for neighbor in adjacency_list[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                # ... rest of logic

Why It's Wrong:

• If node 0 reaches node 5, node 5 gets marked as visited globally
• When we later start BFS from node 1, we can't reach node 5 even if there's a path from 1 to 5
• Node 1 won't be recorded as an ancestor of node 5

The Solution: Create a fresh visited set for each BFS traversal:

# CORRECT: Local visited set for each BFS
def bfs(start_node):
    queue = deque([start_node])
    visited = {start_node}  # Fresh set for this BFS
    # ... rest of logic

3. Including a Node as Its Own Ancestor

The Pitfall: Accidentally adding a node to its own ancestor list when there's a path from the node back to itself (though this shouldn't happen in a valid DAG).

Example Scenario:

# WRONG: Not preventing self-ancestor
while queue:
    current = queue.popleft()
    for neighbor in adjacency_list[current]:
        ancestors[neighbor].append(start_node)  # What if neighbor == start_node?

The Solution: The correct implementation prevents this by marking the start node as visited before beginning the traversal, ensuring we never revisit it:

# CORRECT: Start node marked as visited
visited = {start_node}  # Prevents revisiting start_node

4. Inefficient Duplicate Prevention

The Pitfall: Adding the same ancestor multiple times to a node's ancestor list when there are multiple paths between them.

Example: If there are paths 0→1→3 and 0→2→3, node 0 might be added twice as an ancestor of node 3.

Why the Current Solution Avoids This: The BFS approach with a visited set naturally prevents duplicates. Once a node is visited during a single BFS, it won't be visited again in that same traversal, so each ancestor is added exactly once.

Alternative Approach That Could Have This Issue:

# RISKY: DFS without proper tracking could add duplicates
def dfs(current, ancestor, visited_in_path):
    for neighbor in adjacency_list[current]:
        ancestors[neighbor].append(ancestor)  # Might add duplicates!
        dfs(neighbor, ancestor, visited_in_path)