This is a simple container for implementing a retroactive disjoint set. It supports joining sets and querying their proximity online, and also creating branches of versions instantly. The time complexity is \(O(n \log^2 n)\), while its memory complexity is \(O(n \log n)\). However this version seemed to have a constant error, id est failed by allocating too much memory. I updated the template this afternoon, and came to optimize this and reduced the memory to around 150MB.

It ‘s quite simple to use this template. All you need to do is to initialize the template, build it and fork it. To initialize, do the following:

int n = 5000;
retroactive_disjoint_set set;
set.init(n);

To create branches, you need to specify the older version by its version number. The version number could be arbitrary integers, but not floating point numbers or 64 bit integers. To maintain maximum compatibility, we advise you against using timestamps of large values or less than 0. If no version number is set, we default the base version to #0:

int old_time = 3;
int new_time = 7;
set.fork(new_time, old_time);
// Creating another from base version
set.fork(new_time);
// set.fork(new_time, 0);

To combine two sets, simply specify one arbitrary element in each individual set and call the join command:

set.fork(6, 0);
// Should output "False" for the line below
std::cout << set.joined(6, 3468, 3580) ? "True" : "False" << std::endl;
// Join the two sets by the two elements
set.join(6, 3468, 3580);
// Should output "True" for the line below
std::cout << set.joined(6, 3468, 3580) ? "True" : "False" << std::endl;

If you are looking for the template, you can find it by expanding the article and look below. This works perfectly well at most places. But if you find a bug, don’ t ask me. I don ‘t know very clearly about this, and it’ s not very efficient, though.


#include "rta_array.cpp"

struct rds_unit {
    int par, size;
    rds_unit(void) { par = size = 0; }
    rds_unit(int _1, int _2) { par = _1, size = _2; }
};
rds_unit ra_generator(int pos) {
    rds_unit ru(pos, 1);
    return ru;
}

class retroactive_disjoint_set
{
private:
    int n;
    retroactive_array<rds_unit> ra;
public:
    void fork(int time, int time_old = 0) {
        ra.fork(time, time_old);
        return ; }
    int find(int time, int p)
    {
        rds_unit q_ru = ra.get(time, p);
        int q = q_ru.par;
        if (p == q)
            return p;
        return find(time, q);
    }
    bool joined(int time, int p, int q)
    {
        p = find(time, p);
        q = find(time, q);
        if (p == q)
            return true;
        return false;
    }
    void join(int time, int p, int q)
    {
        p = find(time, p);
        q = find(time, q);
        if (p == q)
            return ;
        rds_unit p_ru = ra.get(time, p),
                 q_ru = ra.get(time, q);
        // Ensure rank balance
        if (p_ru.size > q_ru.size)
            std::swap(p, q),
            std::swap(p_ru, q_ru);
        // Joining
        q_ru.size += p_ru.size;
        p_ru.par = q;
        ra.set(time, p, p_ru);
        ra.set(time, q, q_ru);
        return ;
    }
    void init(int n)
    {
        this->n = n;
        ra.init(n, ra_generator);
        return ;
    }
};

The following is a previous template, which costs more memory and time. We advise you against using the deprecated version.


#include "rta_array_old.cpp"

class retroactive_disjoint_set
{
private:
    struct rds_unit {
        int par, size;
        rds_unit(void) { par = size = 0; }
        rds_unit(int _1, int _2) { par = _1, size = _2; }
    }; int n;
    retroactive_array<rds_unit> ra;
public:
    void fork(int time, int time_old = 0) {
        ra.fork(time, time_old);
        return ; }
    int find(int time, int p)
    {
        rds_unit q_ru = ra[time][p];
        int q = q_ru.par;
        if (p == q)
            return p;
        return find(time, q);
    }
    bool joined(int time, int p, int q)
    {
        p = find(time, p);
        q = find(time, q);
        if (p == q)
            return true;
        return false;
    }
    void join(int time, int p, int q)
    {
        p = find(time, p);
        q = find(time, q);
        if (p == q)
            return ;
        rds_unit p_ru = ra[time][p],
                 q_ru = ra[time][q];
        // Ensure rank balance
        if (p_ru.size > q_ru.size)
            swap(p, q),
            swap(p_ru, q_ru);
        // Joining
        q_ru.size += p_ru.size;
        p_ru.par = q;
        ra[time][p] = p_ru;
        ra[time][q] = q_ru;
        return ;
    }
    void init(int n)
    {
        this->n = n;
        rds_unit ru(0, 1);
        ra.init(n, rds_unit(0, 1));
        for (int i = 1; i <= n; i++) {
            ru = rds_unit(i, 1);
            ra[0][i] = ru;
        }
        return ;
    }
};