# Finding topologically sorted connected components in directed acyclic graph

I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am finding it surprisingly hard.

Assuming a directed acyclic graph, is it possible to simultaneously find the list of connected components while at the same time topologically sorting the nodes in each of the components?

To clarify, the output would be a list of components, where each component is a topological order of the nodes contained in that component.

Bonus points if the list of connected components is sorted following the insertion order of nodes in the graph (i.e. the first connected component will contain the first node ever inserted in the graph, regardless of global topological order; etc for subsequent components).

Standard algorithms for computing strongly connected components label each vertex with a number indicating which component it is part of. Then, you can use that to construct the "metagraph" of components (where each component of the graph is a vertex of the metagraph, and there is an edge $$i \to j$$ in the metagraph iff there is an edge $$v \to w$$ in the original graph where $$v$$ is in component $$i$$ and $$w$$ is in component $$j$$) in linear time. Finally, you can apply a topological sorting algorithm on the metagraph.