(* 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);