// 06-09-2011 Edit: sz array was initialized to be all 0 instead of 1
// From Wikipedia: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
// In computing, a disjoint-set data structure is a data structure that keeps track
// of a set of elements partitioned into a number of disjoint (nonoverlapping)
// subsets. A union-find algorithm is an algorithm that performs two useful
// operations on such a data structure:
// Find: Determine which set a particular element is in. Also useful for
// determining if two elements are in the same set.
// Union: Combine or merge two sets into a single set.
// Implementation from: http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
/// Quick-find... Union is O(N), Flat Trees
/// Quick-union... Trees are tall, Find is O(N), Find requires union
/// Overall: O(MN) -- M union-find ops on a set of N objects
type QuickUnion (N) =
//Parent index, id[i] is parent of i
let mutable id : int[] = Array.init N (fun i -> i)
let root i =
let mutable q = i
while (q <> id.[q]) do q <- id.[q]
q
member t.find(p, q) =
root(p) = root(q)
member t.unite(p, q) =
let i = root(p)
let j = root(q)
id.[i] = j;
/// Weighted QuickUnion
/// Now with logN union, lgN find
/// Overall: O(N+MLogN) -- M union-find ops on a set of N objects
type WeightedQuickUnion (N) =
//Parent index, id[i] is parent of i
let id : int[] = Array.init N (fun i -> i)
//Number of elements rooted at i
let sz : int[] = Array.create N 1
let root i =
let mutable q = i
while (q <> id.[q]) do q <- id.[q]
q
member t.find(p, q) =
root(p) = root(q)
member t.unite(p, q) =
let i = root(p)
let j = root(q)
if sz.[i] < sz.[j] then id.[i] <- j; sz.[j] <- sz.[j] + sz.[i]
else id.[j] <- i; sz.[i] <- sz.[i] + sz.[j]
/// Weighted quick-union with path compression
/// Overall: O((M+N)lg*N) -- M union-find ops on a set of N objects
type QuickUWPC (N) =
//Parent index, id[i] is parent of i
let id : int[] = Array.init N (fun i -> i)
//Number of elements rooted at i
let sz : int[] = Array.create N 1
let root i =
let mutable q = i
while (q <> id.[q]) do
id.[q] <- id.[id.[q]]
q <- id.[q]
q
member t.find(p, q) =
root(p) = root(q)
member t.unite(p, q) =
let i = root(p)
let j = root(q)
if sz.[i] < sz.[j] then id.[i] <- j; sz.[j] <- sz.[j] + sz.[i]
else id.[j] <- i; sz.[i] <- sz.[i] + sz.[j]