Dérouler Kosaraju

Premier parcours, en partant de $a$ et en suivant les listes dans l'ordre donné. La descente est $a,b,c,d,h,g,f$ ; $f$ n'a que $g$ comme successeur, déjà vu, donc $f$ termine le premier. En remontant :

ordre de FIN de traitement : f  g  h  d  c  e  b  a
pile (le dernier fini en tete) : a  b  e  c  d  h  g  f

Second parcours, sur $G^{\mathsf{T}}$, en suivant la pile :

On retrouve les trois composantes de l'exercice « Décomposer à la main ».

Ce qu'on remarque, et c'est un résultat. La numérotation $C_0,C_1,C_2$ est un tri topologique du quotient : les arcs $C_0\to C_1$, $C_0\to C_2$, $C_1\to C_2$ vont tous d'un numéro petit vers un numéro grand. Ce n'est pas un hasard de l'exemple. Une vérification sur $5000$ graphes orientés tirés au hasard ne trouve aucun arc du quotient allant d'un grand numéro vers un petit.

Pourquoi : le second parcours démarre toujours sur une composante source du reste du quotient de $G$ (c'est l'argument du chapitre), et l'épuise avant de passer à la suivante. Il traite donc les composantes dans un ordre où toute composante vient après celles qui pointent vers elle.

Conséquence pratique : Kosaraju rend, gratuitement, un tri topologique du quotient. On n'a pas à le recalculer — et le problème « 2-sat : du critère au modèle » s'en sert pour construire un modèle de 2-sat.