Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
type IndependentSets(n) =
let rank, boss = Array.create n 0, Array.init n (fun x->x)
member this.find(x) =
if boss.[x] = x then x else boss.[x] <- this.find(boss.[x]); boss.[x]
member this.union(x,y) =
let a,b = this.find(x), this.find(y)
if (rank.[a] < rank.[b]) then boss.[a] <- b
if (rank.[a] > rank.[b]) then boss.[b] <- a
if (rank.[a] = rank.[b]) then boss.[b] <- a; rank.[a] <- rank.[a] + 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment