Strongly connected components of this digraph

directed graphsdiscrete mathematicsgraph theory

Consider the following Digraph

Digraph

Identify the strongly-connected components of D, and sketch the associated condensation digraph.

My attempt:

Since $a \rightarrow b \rightarrow c$ and $e \rightarrow f \rightarrow d$ form a cycle they are strongly connected. The remaining nodes are $h,i,j$. So the strongly connect components of D are $C_i = \{\{a, b, c\}, \{e, f, d\}, \{h\}, \{i\}, \{j\}\}$. So the condensation graph is $C_1 \rightarrow C_2 \rightarrow \preceq \rightarrow C_3 \rightarrow \preceq C_4 \rightarrow \preceq \rightarrow C_5$.

I'm new to graph theory, but I'm convinced this is correct. Could I get feedback on my solution

Best Answer

Your SCCs are correct. I'm not sure how to parse your description of the condensation, but its edges should be $C_1\to C_2$, $C_2\to C_3$, $C_2\to C_4$ and $C_2\to C_5$.