# Transitive Closure vs Reachability in Graphs

I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph G(V, E) and is the time complexity not O(|V|+|E|):

Use Kosaraju's to compute SCCs (strongly connected components) -- O(|V| + |E|)

Create a DAG from the SCCs as (super)nodes -- O(|V| + |E|)

In a single supernode, reachability of all nodes is the same and equal to the union of the nodes in the containing supernode plus the reachable supernodes in the DAG -- O(|V| + |E|) to compute reachability in the DAG and O(|V| * |V|) total to compute reachability sets for all nodes

These reachability sets do constitute the transitive closure of the graph wholly, right?
But there aren't any O(|V| + |E|) transitive closure algorithms around.
What am I missing?

• Calculate the transitive closure as a relation. This cannot run in time $$O(|V|+|E|)$$, since the output could be bigger than that (consider a directed path, for example).
• Calculate enough information to be able to answer oracle queries to the transitive closure in $$O(1)$$. Even in this case, the algorithm doesn't seem to run in time $$O(|V|+|E|)$$. Hopefully the link would make it clear why.
• By “transitive closure” as a relation, I mean all pairs of points $(x,y)$ such that $y$ is reachable from $x$. Regarding oracle queries, you’re probably correct, but I suggest reading the link. – Yuval Filmus Jun 5 '19 at 16:01