Quick union

Quick union, at the contrary of quick find, favors having a quick union over find. It uses the same data structure as Quick find speeding up the union function. Each ids entry will be the name of another element in the same component (also possibly itself).

The find function will follow each ids value until reaching the root, which is the element that links to itself. Two elements are in the same component if they share the same root. The union function will just obtain the roots from the two components passed as arguments and, if they are different, it will link them assigning one of the roots ancestor the other one.

impl UnionFind for QuickUnion {
    /// Merges two components if the two elements are in different components.
    fn union(&mut self, p: usize, q: usize) {
        let p_root = self.find(p);
        let q_root = self.find(q);

        if p_root != q_root {
            self.ids[p_root] = q_root;
            self.count -= 1;
        }
    }

    /// Returns the component identifier for a given element.
    fn find(&mut self, mut i: usize) -> usize {
        while i != self.ids[i] {
            i = self.ids[i];
        }

        i
    }

    /// Returns the number of components.
    fn components(&self) -> usize {
        self.count
    }
}

The details of how the algorithm process looks like is described in its unit test:

#[test]
fn test_quick_union() {
    let mut alg = QuickUnion::new(10);

    // Initial state: all elements roots are themselves and their root sizes are 1. The total
    // components are 10.
    let mut expected_find_pos = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    //
    assert_eq!(alg.components(), 10);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 4 and 3, both elements have different roots, 4 and 3 respectively so they are in
    // different components and can be joined so the root of p(4) is updated to the root of q(3)
    // and the total components are 9.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 2, 3, 3, 5, 6, 7, 8, 9];
    //                            ^  ^
    alg.union(4, 3);
    assert_eq!(alg.components(), 9);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 3 and 8, their roots are 3 and 8 respectively so like in the previous iteration the
    // root of p(3) is updated to the root of q(8). The total components are 8.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 2, 8, 3, 5, 6, 7, 8, 9];
    //                            ^              ^
    alg.union(3, 8);
    assert_eq!(alg.components(), 8);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 6 and 5, their roots are 6 and 5 respectively so the root of p(6) is updated to the
    // root of q(5) which is 5. The total components are 7.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 2, 8, 3, 5, 5, 7, 8, 9];
    //                                  ^  ^
    alg.union(6, 5);
    assert_eq!(alg.components(), 7);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 9 and 4, their roots are 9 and 8 respectively so the root of p(9) is udpated to the
    // root of q(4) which is 8. The total components are 6.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 2, 8, 3, 5, 5, 7, 8, 8];
    //                            ^  ^              ^
    alg.union(9, 4);
    assert_eq!(alg.components(), 6);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 2 and 1, their roots are 2 and 1 respectively so the root of p(2) is updated to the
    // root of q(1) which is 1. The total components are 5.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 1, 8, 3, 5, 5, 7, 8, 8];
    //                      ^  ^
    alg.union(2, 1);
    assert_eq!(alg.components(), 5);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 8 and 9, their roots are the same so nothing else is needed.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 1, 8, 3, 5, 5, 7, 8, 8];
    //                                           ^  ^
    alg.union(8, 9);
    assert_eq!(alg.components(), 5);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 5 and 0, their roots are 5 and 0 respectively so the root of p(5) is updated to the
    // root of q(0) which is 0. The total components are 4.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 1, 8, 3, 0, 5, 7, 8, 8];
    //                   ^              ^
    alg.union(5, 0);
    assert_eq!(alg.components(), 4);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 7 and 2, their roots are 7 and 1 respectively so the root of p(7) is updated to the
    // root of q(2) which is 1. The total components are 3.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [0, 1, 1, 8, 3, 0, 5, 1, 8, 8];
    //                         ^              ^
    alg.union(7, 2);
    assert_eq!(alg.components(), 3);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 6 and 1, their roots are 0 and 1 respectively so the root of p(6), which is 0, is
    // updated to the root of q(1) which is 1. The total components are 2.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [1, 1, 1, 8, 3, 0, 5, 1, 8, 8];
    //                   ^  ^           ^  ^
    alg.union(6, 1);
    assert_eq!(alg.components(), 2);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 1 and 0, their roots are the same 1 so nothing else is needed.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [1, 1, 1, 8, 3, 0, 5, 1, 8, 8];
    //                   ^  ^
    alg.union(1, 0);
    assert_eq!(alg.components(), 2);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }

    // Union 6 and 7, like in the last iteration their roots are the same 1 so nothing else is
    // needed.
    //                   0  1  2  3  4  5  6  7  8  9
    expected_find_pos = [1, 1, 1, 8, 3, 0, 5, 1, 8, 8];
    //                   ^  ^           ^  ^  ^
    alg.union(6, 7);
    assert_eq!(alg.components(), 2);
    for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
        assert_eq!(alg.ids[i], expected_find, "i={}", i);
    }
}

Although, initially, quick union seems faster than quick find because it does not need to completely traverse the entire vector on each union, it is not guaranteed so. There are worst case scenarios where the complexity is still quadratic N².

For example, having input pairs in the form of: 0 1, 0 2, 0 3, etc. we will end up with a tree after N-1 of such pairs with a height of N-1, with 0 linked to 1, 1 to 2 and so forth. The number of accesses to the vector for the 0 i union call is 2i + 2 (the element 0 is at depth i and the element i is at depth 0) thus the total number of vector accesses of the find function for these N pairs is: 1(1 + 2 + ... + N) which is ~N².

The full source code can be found here.