(* dict nod -> reprez *)
(* dict reprez -> multimea nodurilor *)

module M = Map.Make(String)
module S = Set.Make(String)
  
let rec find x dict =
  try find (M.find x dict) dict
  with Not_found -> x

(* drep: de la nod la nod echivalent; radacina = reprezentant *)
(* dgrup: dictionar cu multimea nodurilor reprezentate de un nod, initial vid *)
    
let union (drep, dgrup) (x, y)  =
  let rx = find x drep
  and ry = find y drep
  in if rx = ry then (drep, dgrup)
    else
      let nodeset n = try M.find n dgrup with Not_found -> S.empty
      in (M.add rx ry drep,        (* leaga pe rx la ry *)
          (* adauga la nodurile lui ry pe rx, si nodurile lui rx si ry *)
          (* scoate rx din dictionarul cu reprezentanti *)
          M.add ry (S.add rx (S.union (nodeset rx) (nodeset ry)))
                                (M.remove rx dgrup))

let edges = [ ("a", "b"); ("b", "e"); ("e", "a");
              ("c", "d"); ("d", "c");
              ("d", "h"); ("h", "d"); ("h", "g"); ("f", "g"); ("g", "f") ]

let (drep, dgrup) = List.fold_left union (M.empty, M.empty) edges

;;
M.iter (fun k v ->
  print_string (k ^ "->"); S.iter print_string v; print_newline()) dgrup
;;
find "a" drep
  

This document was generated using caml2html