# What is the relation between Topological Sort and Strongly Connected Components?

Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex.

I find difficult to find an explaination because Topological Sorting algorithm is applied on DAGs, whereas the other one can be applied on any type of graph, especially cyclic.

Hope my question makes sense, thank you in advance.

Given a graph $$G$$, construct the graph $$G'$$ in which every connected component of $$G$$ is a node, and two nodes in $$G'$$ have a (directed) edge if there is an edge between any two nodes in the connected components they represent in $$G$$.
Sometimes this graph $$G'$$ is known as the "supergraph" of $$G$$.
Now, its not hard to see why $$G'$$ is a DAG, and hence has a topological sort, which induces a partial ordering on $$G'$$.
You can "extend" this partial ordering into $$G$$ by saying that two nodes in the same connected component will be "the same", and two nodes from different components will relate if their respective components relate in $$G'$$.
• Thank you for your kind answer. It makes sense. A topological ordering can't be performed on cyclic graphs, but if there's a cycle, then it resides entirely in the same $SCC$ Dec 11 '21 at 11:17