1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
module Mint = Tools.Mint
module UF : sig
type uf
val create : unit -> uf
val find : uf -> int -> int
val union : uf -> int -> int -> int
val dup : uf -> uf
end = struct
type uf = (int Mint.t) ref
let create () =
ref Mint.empty
let find (uf : uf) =
let rec doit (x : int) =
match Mint.find_opt x !uf with
| None -> x
| Some y when x = y -> x
| Some y -> doit y
in fun x -> doit x
let union (uf : uf) (x : int) (y : int) =
let x = find uf x in
let y = find uf y in
if x < y
then (uf := Mint.add y x !uf; x)
else if x > y
then (uf := Mint.add x y !uf; y)
else x
let dup (uf : uf) =
ref !uf
end