// 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]