Class QuickUnionUF

src/common/uf.rs:62–65

In particular, suppose that we use quick-find for the dynamic connectivity problem and wind up with a single component. This requires at least N - 1 calls to union(), and, consequently, at least (N + 3)(N - 1) ~ N^2 array accesses —- we are led immediately to the hypothesis that dynamic connectivity with quick-find can be a quadratic-time process. Suppose that the input pairs come in the order 0-

/// and site i at depth 0). Thus, the total number of array accesses for the
/// find() operations for these N pairs is 2 (1 + 2 + . . . + N ) ~ N^2
pub struct QuickUnionUF {
    parent: Vec<usize>, // parent[i] = parent of i
    count: usize,       // number of components
}

/// Rather than arbitrarily connecting the second tree to the first for union(),
/// we keep track of the size of each tree and always connect the smaller tree to