= Solution
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 \b[$\{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.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/algorithms-strong-components.png]
{title=Seven vertices with three strongly connected components and their condensation}
{description=An original example. Internal cycles provide mutual reachability; the two forward connecting edges cannot merge distinct components.}
Back to article page
