\cdot c^2 \cdot n)$ time.

We fix some $S = \{ v_1, \dots, v_{n_S} \}$. We use $S_v$ to denote the SCC to which the vertex $v \in V({G_\ell^{\operatorname{rel}}})$ belongs and $\mathcal{T}_B = \{ S_u \mid \exists w.\; wu \in B \}$ to denote the SCCs containing a terminal vertex of at least one arc in $B \subseteq A({G_\ell^{\operatorname{rel}}})$. Note that in the subsequent proof the arcs in $B$ will all have their initial vertex in $S$. Moreover, the arc set $B_i$ contains only arcs having a initial vertex in $\{v_1, \ldots, v_i\} \subseteq S$ and we have $\mathcal{T}_{B_i} = \{ S_u \mid \exists j \le i.\; v_ju \in A({G_\ell^{\operatorname{rel}}})\}$. (See of \[scc:dp\] for the computation of the arc set $B_i$.)

In order to show that the output of satisfies the property of  \[def:mcc1\], we prove the following stronger claim.

For any $i \in \{ 0, \ldots, n_S \}$ and any set $\mathcal{T} \subseteq \mathcal{T}_{B_i}$ of SCC, the arc set $D_i(\mathcal{T})$ contains exactly one arc that starts in $\{v_1,\ldots,v_i\}$ and ends inside $S'$ for each $S' \in \mathcal{T}$ and contains no other arc.

We first show by induction that the claim holds after the initialization phase (). It holds for 