trouver toutes les composantes connexes d'un graphe

[comersy]

let dfs g r =
let seen = Array.make g.n (0,false) in
for i = 0 to g.n -1 do
seen.(i) <- (i,false)
done;
let rec aux v =
if not (snd seen.(v)) then (
seen.(v) <- (v,true);
List.iter aux (g.adj v))
in aux r;
seen;;

let list_of_array l =
let n = List.length l in
let t = Array.make n (0,false) in
List.iteri (Array.set t) l;
t;;

let connexe g =
let compo_connexe = ref [] in (* Liste qui contient chaque composantes connexes )
let rec aux seen =
if Array.length seen = 0
then ()
else
let compo = ref [] in ( Liste qui contient une composante connexe*)
let seen_false = ref [] in (* Liste qui contient les couples (indice,false): indices pas dans la CC )
for j = 0 to Array.length seen - 1 do
if snd seen.(j) then
compo := j::!compo ( Indice dans la CC -> compo*)
else
seen_false := (j,false)::!seen_false; (* Indice pas dans la CC -> seen_false*)
done;
compo_connexe := !compo::!compo_connexe; (* On ajoute la CC en cours dans la liste des CC )
aux (list_of_array !seen_false) ( On rapelle aux avec les indices pas dans la CC pour ne pas mettre deux fois la même CC *)
in aux (dfs g 0);
!compo_connexe;;