Le piège de l'ordre

Trois sommets suffisent : $a\leftrightarrow b$ et $c\to a$, c'est-à-dire les arcs $a\to b$, $b\to a$, $c\to a$. Les composantes réelles sont $\{a,b\}$ et $\{c\}$.

La version correcte : le premier parcours part de $a$, descend en $b$, revient ; $b$ termine, puis $a$, puis $c$. Ordre de fin : $b,a,c$ ; pile : $c,a,b$. On part de $c$ dans $G^{\mathsf{T}}$ : les prédécesseurs de $c$ dans $G$ sont vides, donc $G^{\mathsf{T}}$ n'a aucun arc sortant de $c$, et l'on ramasse $\{c\}$ seul. Puis $a$ : dans $G^{\mathsf{T}}$, $a\to c$ (déjà marqué) et $a\to b$, d'où $\{a,b\}$. Résultat mesuré : c:0 a:1 b:1. Correct.

La version fautive : l'ordre de découverte est $a,b,c$. On part donc de $a$ dans $G^{\mathsf{T}}$, où $a$ a pour successeurs $b$ et $c$ — puisque $b\to a$ et $c\to a$ dans $G$. Le parcours ramasse les trois. Résultat mesuré : a:0 b:0 c:0, une seule composante $\{a,b,c\}$. Faux.

La cause, en une phrase. L'ordre de découverte ne dit rien sur la place d'un sommet dans le quotient : $a$ a été découvert en premier simplement parce qu'il porte le numéro $0$. L'ordre de fin, lui, porte une information : le dernier sommet à terminer appartient nécessairement à une composante source, car s'il existait un arc entrant venant d'une autre composante, le sommet source de cet arc aurait terminé après lui. C'est ce théorème-là que l'algorithme exploite, et il ne vaut que pour l'ordre de fin.

Et remarquer que le contre-exemple est minuscule. Un jeu de tests contenant un seul graphe à trois sommets et trois arcs aurait suffi à révéler la faute. C'est la partition en classes d'équivalence du chapitre chap:discipline : le cas « une composante contient le sommet de départ, une autre pointe vers elle » est une classe à part entière.