Composantes fortement connexes et couplages

• Faire un parcours en profondeur de $G$ et empiler chaque sommet quand on a fini de le traiter — c'est exactement le tri topologique du chapitre chap:parcours.
• Construire $G^{\mathsf{T}}$, le graphe transposé : tous les arcs retournés.
• Parcourir $G^{\mathsf{T}}$ en repartant des sommets dans l'ordre de la pile. Chaque parcours atteint exactement une composante.

(* Renvoie un tableau comp tel que comp.(u) est le numéro de la composante
   fortement connexe de u. Complexité : Theta(n + m). *)
let kosaraju g =
  let n = Array.length g in
  (* 1. ordre de fin de traitement *)
  let vu = Array.make n false and ordre = ref [] in
  let rec descendre u =
    vu.(u) <- true;
    List.iter (fun v -> if not vu.(v) then descendre v) g.(u);
    ordre := u :: !ordre
  in
  for s = 0 to n - 1 do if not vu.(s) then descendre s done;
  (* 2. le graphe transposé *)
  let gt = Array.make n [] in
  Array.iteri (fun u l -> List.iter (fun v -> gt.(v) <- u :: gt.(v)) l) g;
  (* 3. parcours de gt dans cet ordre *)
  let comp = Array.make n (-1) and k = ref 0 in
  let rec marquer u =
    comp.(u) <- !k;
    List.iter (fun v -> if comp.(v) = -1 then marquer v) gt.(u)
  in
  List.iter (fun u -> if comp.(u) = -1 then begin marquer u; incr k end) !ordre;
  comp

On échange le long du chemin : ce qui était dans $M$ en sort, ce qui était dehors y entre. Le couplage reste valide — chaque sommet intermédiaire perd une arête et en gagne une — et les deux extrémités, libres, deviennent saturées. Le cardinal augmente d'exactement un.

Le programme précise : « on se limite à une approche élémentaire ; l'algorithme de Hopcroft-Karp n'est pas au programme ».

(* Couplage maximum d'un graphe biparti. g.(u) est la liste des voisins de u
   dans la partie droite. conj.(v) = Some u si v est couplé à u.
   Complexité : O(n·m). *)
let couplage_maximum g nd =
  let ng = Array.length g in
  let conj = Array.make nd None in
  (* cherche un chemin augmentant depuis u ; vu évite de tourner en rond *)
  let rec augmenter vu u =
    List.exists (fun v ->
      if vu.(v) then false
      else begin
        vu.(v) <- true;
        match conj.(v) with
        | None -> conj.(v) <- Some u; true              (* v est libre : on prend *)
        | Some w ->
            (* v est pris par w : w peut-il se recaser AILLEURS ? *)
            if augmenter vu w then begin conj.(v) <- Some u; true end
            else false
      end) g.(u)
  in
  let taille = ref 0 in
  for u = 0 to ng - 1 do
    if augmenter (Array.make nd false) u then incr taille
  done;
  !taille

La ligne qui porte tout est le Some w : au lieu d'abandonner parce que $v$ est déjà pris, on demande à son partenaire actuel de se recaser ailleurs. C'est la remise en cause qu'un glouton s'interdit — et la récursion la propage aussi loin qu'il faut.