Prerequisites: Graphs, DFS/BFS, Topological order.
Problem: Given a Directed Acyclic Graph (DAG) with N nodes numbered from 0 to N - 1, print in sorted ascending order, the ancestors of ith node for each node 0 to N - 1. An ancestor of a node u in this context is defined as a node v that can be reached from u through a set of directed edges in the graph.
Solution Approach: The core of the solution’s algorithm is a breadth-first search (BFS) traversal(in the same manner we use it to find topological ordering) of the Directed Acyclic Graph starting from nodes with an indegree of 0. For each node processed in the BFS, its ancestors are updated by adding its own ancestors and the ancestors of its adjacent nodes. This is achieved by maintaining a set for each node to store its ancestors. The BFS continues until all nodes have been processed, ensuring that every node’s ancestors are correctly identified. Finally, the ancestors for each node are printed in sorted ascending order, as determined by the set data structure.
Time complexity: O(M + NlogN) as we are using BFS and also using set data structure which has logN time for insert operation.
Space complexity: O(N) as we need to use a queue and set in BFS.