Create a map of connected nodes from a list of edges in $O(n^2)$

Question

I have a directed graph. It may or may not be a DAG.

I would like to create a map in $O(n^2)$ time to find all nodes that are accessible from a node on a directed path, where $n$ is number of vertices.

$G := $

A  —> B —> C
|          ^
v          |
D —————————

M = create_map(G) //in $O(n^2)$ time

• M(A) should be {B, C, D}
• M(B) and M(D) should be {C}
• M(C) should be $\emptyset$

How is it possible?

Answer 1

Construct the Strongly Connected Components graph (this can be done in $O(|E|+|V|) \le O(|V|^2$)). You can then calculate which nodes is reachable from every node naively in $O(|V|^2)$ from this graph.