disjoint_set/disjoint_set.cpp

#include <iostream>
#include "disjoint_set.hpp"

#define endl '\n'

using namespace std;

void print(DisjointSet *ds)
{
    cout << ds->root(0) << " " << ds->size(0) << " " << ds->root(1) << " " << ds->size(1) << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // Creates a disjoint set that allows undo last action.
    // It creates a separate array history to allow this.
    auto ds = disjoint_set()->with_undo()->init(2);
    print(ds);
    // 0 | root 0 | size 1
    // 1 | root 1 | size 1

    ds->merge(0, 1);
    print(ds);
    // 0 | root 1 | size 2
    // 1 | root 1 | size 2

    ds->undo();
    print(ds);
    // 0 | root 0 | size 1
    // 1 | root 1 | size 1

    // This disjoint set doesn't allow to undo (it doesn't build history vector)
    // but has the same base type that the former disjoint set. It can be passed
    // to the same function and they expose the same api ...
    //  with some caveat see below
    ds = disjoint_set()->init(2);
    print(ds);
    // 0 | root 0 | size 1
    // 1 | root 1 | size 1

    ds->merge(0, 1);
    print(ds);
    // 0 | root 1 | size 2
    // 1 | root 1 | size 2

    // Caveat: This disjoint expose undo function, but it will throw an error if
    // used since it is not really available.
    // ds->undo();
    // print(ds);

    return 0;
}