Décomposer à la main

Les composantes — on cherche les cycles, puis on les recolle :

$$C_1=\{a,b,e\},C_2=\{c,d,h\},C_3=\{f,g\}.$$

Justification de $C_1$ : $a\to b\to e\to a$ est un cycle, donc les trois sont mutuellement accessibles. De $C_2$ : $c\to d\to c$, et $d\to h\to d$. De $C_3$ : $f\to g\to f$. Et rien de plus ne peut fusionner : depuis $c$ on n'atteint jamais $a$, car aucun arc ne sort de $\{c,d,h,f,g\}$ vers $\{a,b,e\}$.

Le quotient contient trois arcs, obtenus en projetant les arcs inter-composantes :

$$C_1⟶C_2(b\to c),C_1⟶C_3(b\to f,e\to f),C_2⟶C_3(c\to g,h\to g).$$

Il est acyclique : $C_1$ n'a aucun arc entrant, $C_3$ aucun sortant, et il n'y a pas d'arc $C_2\to C_1$ ni $C_3\to C_2$. Un tri topologique est $C_1,C_2,C_3$.

Ce que la méthode a de mécanique. On n'a pas cherché les composantes « au flair » : on a d'abord repéré les cycles élémentaires, puis vérifié qu'aucun arc ne permettait de revenir en arrière entre les paquets obtenus. C'est très exactement ce que Kosaraju automatise — et l'exercice « Dérouler Kosaraju » le déroule sur ce même graphe.