//
// Created by Robert Kramer on 11/30/21.
//

#include "DisjointSet.h"

DisjointSet::DisjointSet(uint32_t nElements) {

    elements = new uint32_t[nElements];
    rank = new uint8_t[nElements];

    for (uint32_t i=0;i<nElements;i++) {
        elements[i] = i;
        rank[i] = 0;
    }
}

DisjointSet::~DisjointSet() {

    delete[] elements;
}

uint32_t DisjointSet::dsFind(uint32_t el) {

    if (elements[el] != el)
        elements[el] = dsFind(elements[el]);

    return elements[el];
}

void DisjointSet::dsUnion(uint32_t a,uint32_t b) {

    a = dsFind(a);
    b = dsFind(b);

    if (a != b) {
        if (rank[b] > rank[a])
            elements[a] = b;
        else {
            if (rank[a] == rank[b])
                rank[a]++;

            elements[b] = a;
        }
    }
}