Transitive Closure of a graph

Question

Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function.
Show that given a directed graph (not necessarily DAG) $G^{'}$, we can calculate it's transitive closure, $G^{+}=(V, E^{+})$, in time complexity of $O(f(|V|, |E|) + |V| + |E^{+}|)$.
We can assume all the graphs are represented in adjacency matrices.
I don't have any idea for this one. I tried to read stuff about this topic, including in cormen's book, but it didn't lead me to any solution.

Answer 1

Using Kosaraju's algorithm, you can compute the strongly connected components (SCC) of $G$ in linear time.

The metagraph (or graph of the SCC) is well known to be a DAG. You can then compute the transitive closure of the metagraph.

Now to compute $G^+$:

• if $u$ and $v$ are in the same SCC, that means there is an edge from $u$ to $v$ and from $v$ to $u$;
• if $u\in C$ and $v\in C'$ where $C$ and $C'$ are two different SCC such that there is an edge from $C$ to $C'$ in the transitive closure of the metagraph, that means there is an edge from $u$ to $v$ (but not from $v$ to $u$).

All this can be done in the required complexity.