Problème — Kosaraju : pourquoi le second parcours ne déborde pas

1. Soit un arc $C\to C^{\prime }$ dans le quotient. Deux cas, selon celle des deux composantes que le parcours rencontre en premier.

Cas 1 : le parcours entre d'abord dans $C$, en un sommet $u$. Comme $C\to C^{\prime }$, tous les sommets de $C^{\prime }$ sont accessibles depuis $u$ ; comme aucun d'eux n'a encore été vu, la descente depuis $u$ les visitera tous et les terminera avant de terminer $u$ — c'est la propriété d'imbrication des appels récursifs. Donc $f(C)\ge \text{fin}(u)>f(C^{\prime })$.

Cas 2 : le parcours entre d'abord dans $C^{\prime }$, en un sommet $v$. Alors aucun sommet de $C$ n'est accessible depuis $v$ : sinon il y aurait un chemin de $C^{\prime }$ vers $C$, et avec l'arc $C\to C^{\prime }$ un cycle dans le quotient, qui est acyclique. La descente depuis $v$ termine donc tous les sommets de $C^{\prime }$ sans toucher à $C$, et $f(C^{\prime })<f(C)$ car $C$ sera visitée plus tard.

Dans les deux cas $f(C)>f(C^{\prime })$. Autrement dit, trier les composantes par $f$ décroissant est un tri topologique du quotient — c'est la propriété mesurée à l'exercice « Dérouler Kosaraju ».