Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG) Let G = (V, E) be a graph which is hierarchical in the sense that its vertices are arranged in levels/layers (say 1 to k) and an edge can only be from a vertex at level i to a vertex at level i+1. Vertices at level 1 and k are called the roots and the leaves, respectively. The problem is to find all descendant leaves of each root.
For instance, for the following graph,


the answer would be:
1: 12, 13
2: 12, 13
3: 12, 13, 14, 15, 16
4: 14, 15, 16

A naive solution can be to run a DFS for each root which will take O(r(n+m)) time where r is #roots, n is #vertices and m is #edges.

Can we do better?
Another way to see the same graph is that it is a bipartite DAG.
Define $\ell(v)$ to be the leaves reachable from a node $v$. Note the following:


  Lemma 1: For all non-leaf nodes $v$ we have: $$\ell(v) = \cup_{u \in c(v)} \ell(u)$$ where $c(v)$ is the set of all children of $v$.


We now construct an algorithm around this:


Let $A = \{v_1, v_2, \ldots, v_n\}$ be the reverse topological order of nodes in $G$.
For all $v \in A$:


If $v$ is a leaf node, define $\ell(v) = \{v\}$.
Otherwise, define $\ell(v)$ as we did in Lemma 1.



Now the complexity of this is $O(km + n)$ where $k$ is the average cost of union-ing the $\ell$-sets of the children of a non-leaf node. How you go about union-ing the sets is up to you. Standard merging is easy to implement. You could also try using a disjoint-set data structure, but this becomes tricky because a node might have multiple parents.