Composantes connexes

let nb_composantes adj =
  let n = Array.length adj in
  let vu = Array.make n false in
  let rec visite s =
    if not vu.(s) then begin vu.(s) <- true; List.iter visite adj.(s) end
  in
  let c = ref 0 in
  for s = 0 to n - 1 do
    if not vu.(s) then begin c := !c + 1; visite s end
  done;
  !c

Chaque sommet encore non vu lance un parcours qui marque toute sa composante ; on en compte ainsi le nombre. Un graphe connexe a une seule composante.