(* Implémentation Union-Find *)

type unionfind = { pere:int array; rang:int array }

let afficheUF (uf : unionfind) =
  let n = Array.length uf.pere in
  Printf.printf "uf : ";
  for i = 0 to n-1 do
    Printf.printf "(%d->%d) " i uf.pere.(i)
  done;
  print_newline ();;

let creeUF (n:int) : unionfind = { pere = Array.make n (-1); rang = Array.make n 0 };;

(* sans optimisation *)

let rec find (uf:unionfind) (x:int) =
  if uf.pere.(x) = -1 then x else find uf uf.pere.(x);;

let union (uf:unionfind) (x:int) (y:int) =
  let rx = find uf x in
  let ry = find uf y in
    if (rx != ry) then uf.pere.(rx) <- ry;;

(* avec union par rang *)

let rec findR (uf:unionfind) (x:int) = find uf x;; (* pas de changement *)

let unionR (uf:unionfind) (x:int) (y:int) =
  let rx = find uf x in
  let ry = find uf y in
  if (rx != ry) then begin
    if uf.rang.(rx) > uf.rang.(ry) then
      uf.pere.(ry) <- rx (* rang inchangé *)
    else if uf.rang.(rx) < uf.rang.(ry) then 
      uf.pere.(rx) <- ry (* rang inchangé *)
    else begin uf.pere.(rx) <- ry; uf.rang.(ry) <- uf.rang.(ry) + 1 end
  end

(* avec compression de chemins *)

let rec findRC (uf:unionfind) (x:int) =
  if uf.pere.(x) = -1 then x else 
    begin
    let racine = findRC uf uf.pere.(x) 
    in 
    uf.pere.(x) <- racine; racine
    end;;

let unionRC (uf:unionfind) (x:int) (y:int) =
    let rx = findRC uf x in
    let ry = findRC uf y in
    if (rx != ry) then begin
      if uf.rang.(rx) > uf.rang.(ry) then
        uf.pere.(ry) <- rx (* rang inchangé *)
      else if uf.rang.(rx) < uf.rang.(ry) then 
        uf.pere.(rx) <- ry (* rang inchangé *)
      else begin uf.pere.(rx) <- ry; uf.rang.(ry) <- uf.rang.(ry) + 1 end
    end
  ;;

(** Exemple **)

let uf0 = creeUF 5 in
afficheUF uf0;
union uf0 2 4; union uf0 1 3; union uf0 2 3;
afficheUF uf0;;

(** Exemple 2 **)

let rec profondeur (uf:unionfind) (x:int) =
  if uf.pere.(x) = -1 then 0 else 1 + (profondeur uf uf.pere.(x));;

let hauteur_max (uf:unionfind) =
  let maxi = ref 0 in
  for i = 0 to Array.length uf.pere - 1 do
    let h = profondeur uf i in
    if h > !maxi then maxi := h
  done;
  !maxi;;


let n = 1000000 in
let ufBig = creeUF n in
for i = 1 to n do
  let x = Random.int n in
  let y = Random.int n in
  unionRC ufBig x y; (* A modifier avec union et unionR *)
done;
Printf.printf "hauteur maxi : %d\n" (hauteur_max ufBig);