Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 6 / a

A strongly connected component is a maximal set of vertices that are mutually reachable in a directed graph; a vertex reaches itself by a length-zero path. The condensation graph, also called the SCC graph, contracts each such component to one vertex and retains directed edges between different components. It is a Directed acyclic graph, since a cycle of components would make them mutually reachable and therefore one component.

For an original seven-vertex example, take cycles $a\to b\to c\to a$, $d\to e\to d$, $f\to g\to f$, and add $c\to d$, $e\to f$. The three components are $\{a,b,c\}$, $\{d,e\}$ and $\{f,g\}$. Their condensation is the three-vertex directed chain in that order: there is no return edge from a later component to an earlier one.