type cell = { mutable c : int; data : int; mutable father : cell } type t = cell array (* a forest *) let create n = Array.init n (fun i -> let rec cell = { c = 0; data = i; father = cell } in cell) let rec find_aux cell = if cell.father == cell then cell else let r = find_aux cell.father in cell.father <- r; r let find h x = (find_aux h.(x)).data let union h x y = let rx = find_aux h.(x) in let ry = find_aux h.(y) in if rx != ry then begin if rx.c > ry.c then ry.father <- rx else if rx.c < ry.c then rx.father <- ry else begin rx.c <- rx.c + 1; ry.father <- rx end end; h