C++ two-phase path-compression quick-union union find over indices

Question

This is my first C++ class, implementing union find. I’ve tested the implementation very shoddily by checking that unifying two points connects them, and that works. I did a first draft in Python and translated it to C++. I use two buffers to keep track of the traversed items instead of creating a vector each time. Unfortunately I can’t use size_type for the sizes that are used for vectors because that’d require a recursive type. I named the method unify since union is a keyword in C++. I have not tested for performance. I mostly did this by skimming reference materials, tutorials, and examples.

Is this code easy to read, correct, performant, idiomatic, or is there befuddling syntax, bugs, bottlenecks, idiosyncrasies?

#include <vector>
#include <optional>
#include <cstddef>
#include <utility>

class UnionFind {
    std::vector<std::optional<std::size_t>> parents;
    std::vector<std::size_t> crumbs_buf_a;
    std::vector<std::size_t> crumbs_buf_b;
    std::size_t group_count;
    
    std::pair<std::size_t, std::size_t> find_roots(std::size_t a, std::size_t b) {
        std::size_t current;
        std::optional<std::size_t> next;
        crumbs_buf_a[0] = a;
        current = a;
        int i;
        for (i = 1; (next = parents[current]); i++) {
            current = *next;
            crumbs_buf_a[i] = current;
        }
        crumbs_buf_b[0] = b;
        current = b;
        int j;
        for (j = 1; (next = parents[current]); j++) {
            current = *next;
            crumbs_buf_b[j] = current;
        }
        return {i, j};
    }
    
    public:
    UnionFind(std::size_t count) {
        std::optional<std::size_t> nothing = {};
        parents.resize(count, nothing);
        crumbs_buf_a.resize(count, 0);
        crumbs_buf_b.resize(count, 0);
        group_count = count;
    }
    
    bool unify(std::size_t a, std::size_t b) {
        auto [depth_a, depth_b] = find_roots(a, b);
        auto root_a = crumbs_buf_a[depth_a - 1];
        auto root_b = crumbs_buf_b[depth_b - 1];
        if (root_a != root_b) {
            if (depth_a > depth_b)
                for (std::size_t i = 0; i < depth_a; i++)
                    parents[crumbs_buf_a[i]] = root_b;
            else
                for (std::size_t i = 0; i < depth_b; i++)
                    parents[crumbs_buf_b[i]] = root_a;
            group_count--;
            return true;
        }
        return false;
    }
    
    std::size_t find(std::size_t a) {
        auto current = a;
        std::optional<std::size_t> next;
        while ((next = parents[current]))
            current = *next;
        return current;
    }
    
    bool connected(std::size_t a, std::size_t b) {
        return find(a) == find(b);
    }
    
    std::size_t get_group_count() {
        return group_count;
    }
    
    void extend(std::size_t additional = 1) {
        std::optional<std::size_t> nothing = {};
        parents.resize(parents.size() + additional, nothing);
        crumbs_buf_a.resize(crumbs_buf_a.size() + additional, 0);
        crumbs_buf_b.resize(crumbs_buf_b.size() + additional, 0);
        group_count += additional;
    }
};

I used this code to do rudimentary tests:

#include <random>
#include <algorithm>
#include <cassert>
#include <iostream>
#define COUNT 100

int main() {
    UnionFind uf(COUNT);
    std::vector<std::size_t> indices;
    indices.reserve(COUNT);
    for (std::size_t i = 0; i < COUNT; i++)
        indices.push_back(i);
    // mostly copied from https://en.cppreference.com/w/cpp/algorithm/random_shuffle example
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(indices.begin(), indices.end(), g);
    for (std::size_t i = 0; i < COUNT - 1; i++) {
        std::size_t ix_1 = indices[i];
        std::size_t ix_2 = indices[i + 1];
        uf.unify(ix_1, ix_2);
        assert(uf.connected(ix_1, ix_2));
        std::cout << ix_1 << ", " << ix_2 << '\n';
    }
    assert(uf.get_group_count() == 1);
}

Answer 1

Honestly, it seems cumbersome.

First, using a std::size_t instead of a std::optional<std::size_t>, and making the roots their own parent, would half the needed memory.

Next, throwing away the additional buffers will reduce it to a third of that.

The interface need not change for that.

Rewriting the algorithm is simple enough:

// Internal use and if the structure is read-only
FindRoot (array, node):
    while array[node] != node:
        node = array[node]
    return node
// Internal use only
CompressPath (array, node, root):
    while array[node] != node:
        (node, array[node]) = (array[node], root)
    array[node] = root

// For finding pass just one node
Unify (array, nodes):
    root = array.size
    foreach node in nodes:
        root = min(root, FindRoot(array, node))
    foreach node in nodes:
        CompressPath(array, node, root)
    return root

CompressAllPaths(array):
    for node = 0; node < array.size; ++node:
        array[node] = array[array[node]]

Still, while it is good for amortized cost, it is terrible for worst case. For that, more intelligence in picking the new root is needed, wikipedia has a good overview.

---

Regarding your code:

1. Only pass an element to .resize() if default-constructing is undesirable.
2. Avoid the preprocessor, a constexpr constant is generally better.