type t = { rank : int array; father : int array }

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

let rec find_aux f i = 
  if f.(i) == i then 
    i
  else 
    let ri = find_aux f f.(i) in 
    f.(i) <- ri; 
    ri

let find h x = find_aux h.father x
 
let union {rank=r; father=f} x y = 
  let rx = find_aux f x in
  let ry = find_aux f y in
  if rx != ry then begin
    if r.(rx) > r.(ry) then
      f.(ry) <- rx
    else if r.(rx) < r.(ry) then
      f.(rx) <- ry
    else begin
      r.(rx) <- r.(rx) + 1;
      f.(ry) <- rx
    end
  end