(* Structure union-find (programme 72 page 298) en maintenant le nombre
   de classes. *)

type t = {
  rank : int array;
  link : int array;
  mutable num : int;   (* nombre de classes distinctes *)
}

let create n =
  { rank = Array.make n 0;
    link = Array.init n (fun i -> i);
    num  = n; }

let rec find t i =
  let p = t.link.(i) in
  if p = i then
    i
  else begin
    let r = find t p in
    t.link.(i) <- r;
    r
  end

let union t i j =
  let ri = find t i in
  let rj = find t j in
  if ri <> rj then begin
    t.num <- t.num - 1;
    if t.rank.(ri) < t.rank.(rj) then
      t.link.(ri) <- rj
    else begin
      t.link.(rj) <- ri;
      if t.rank.(ri) = t.rank.(rj) then
        t.rank.(ri) <- t.rank.(ri) + 1
    end
  end

let num_classes t = t.num

(* on peut parcourir les différentes classes de la manière suivante *)
let iter_classes f t =
  for i = 0 to Array.length t.link - 1 do
    if t.link.(i) = i then f i
  done

This document was generated using caml2html