(* persistent implementation using a map giving the class id *)

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

type t = int M.t

let create n = M.empty

let find m i = try M.find i m 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
    M.fold
      (fun k rk m -> if rk = ri then M.add k rj m else M.add k rk m)
      m (M.add ri rj M.empty)