(* persistent implementation using two maps:
 * - the map "repr" gives the class id
 * - the inverse map "elts" gives the elements of a class id
 *)

module M = Map.Make(struct type t = int let compare = compare end)
module S = Set.Make(struct type t = int let compare = compare end)

type t = { repr: int M.t; elts: S.t M.t }

let create n = { repr = M.empty; elts = M.empty }

let find m i = try M.find i m.repr with Not_found -> i
    
let union m i j =
  let ri = find m i in
  let rj = find m j in
  if ri = rj then
    m
  else
    let ci = try M.find ri m.elts with Not_found -> S.singleton ri in
    let cj = try M.find rj m.elts with Not_found -> S.singleton rj in
    if S.cardinal ci < S.cardinal cj then
      { repr = S.fold (fun k r -> M.add k rj r) ci m.repr;
	elts = M.add rj (S.union ci cj) (M.remove ri m.elts) }
    else
      { repr = S.fold (fun k r -> M.add k ri r) cj m.repr;
	elts = M.add ri (S.union ci cj) (M.remove rj m.elts) }