Tester la forte connexité en deux parcours

(* Le graphe g est-il fortement connexe ?
   Entree : g.(u) = liste des successeurs de u, n >= 1 sommets.
   Sortie : true ssi tous les sommets sont mutuellement accessibles.
   Complexite : Theta(n + m) -- deux parcours et une transposition. *)
let fortement_connexe g =
  let n = Array.length g in
  let atteint depuis graphe =
    let vu = Array.make n false and compte = ref 0 in
    let rec descendre u =
      vu.(u) <- true; incr compte;
      List.iter (fun v -> if not vu.(v) then descendre v) graphe.(u) in
    descendre depuis; !compte = n in
  let gt = Array.make n [] in
  Array.iteri (fun u l -> List.iter (fun v -> gt.(v) <- u :: gt.(v)) l) g;
  atteint 0 g && atteint 0 gt

Correction. Notons $s=0$ le sommet de départ.

• Le premier parcours vérifie que $s$ atteint tous les sommets.
• Le second vérifie que $s$ atteint tous les sommets dans $G^{\mathsf{T}}$, c'est-à-dire — par l'exercice précédent — que tous les sommets atteignent $s$ dans $G$.

Si les deux tiennent, alors pour $u$ et $v$ quelconques on a $u⇝s⇝v$ : le graphe est fortement connexe. Réciproquement, si le graphe est fortement connexe, les deux parcours réussissent trivialement.

Le point à ne pas manquer : un seul sommet de départ suffit. On pourrait croire qu'il faut essayer tous les sommets ; la forte connexité étant une relation d'équivalence à une seule classe, il suffit de la tester par rapport à un témoin. C'est le même raisonnement qu'en algèbre quand on vérifie qu'un groupe est engendré par un élément.

Complexité : deux parcours en $\Theta (n+m)$ chacun, plus la transposition en $\Theta (n+m)$. Total $\Theta (n+m)$, comme Kosaraju — mais avec deux parcours sans pile d'ordre, et sans tableau de composantes. Quand la question est « oui ou non », il ne faut pas calculer plus que la réponse.