(* Structure union-find pour des éléments d'un type quelconque *)

type 'a elt = { mutable rank: int; mutable link: 'a elt; data: 'a }

let create_node x =
  let rec c = { rank = 0; link = c; data = x } in
  c

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

let union i j =
  let ri = find i in
  let rj = find j in
  if ri != rj then begin
    if ri.rank < rj.rank then
      ri.link <- rj
    else begin
      rj.link <- ri;
      if ri.rank = rj.rank then
        ri.rank <- ri.rank + 1
    end
  end

let data x = x.data

This document was generated using caml2html