Disjoint sets

TBD: Intro

We present three succesive implementations (is it necessary?).

Implementation with simple MF-sets

TBD: Explain

class DisjointSets {

    vector<int> v;

    // find operation
    int find (int i) {
        if (v[i] < 0) return i;
        else return find(v[i]);
    }

public:

    /* Creates n disjoint sets. */
    DisjointSets (int n)
    :   v(n, -1)
    {   }

    /* Finds the class of element i. */
    int operator[] (int i) {
        return find(i);
    }

    /* Merges the classes of elements i and j. */
    void merge (int i, int j) {
        v[i] = j;
    }
};

Implementation with MF-sets by size

TBD: Explain

class DisjointSets {

    vector<int> v;

    // find operation
    int find (int i) {
        if (v[i] < 0) return i;
        else return find(v[i]);
    }

public:

    /* Creates n disjoint sets. */
    DisjointSets (int n)
    :   v(n, -1)
    {   }

    /* Finds the class of element i. */
    int operator[] (int i) {
        return find(i);
    }

    /* Merges the classes of elements i and j. */
    void merge (int i, int j) {
        int ci = find(i);
        int cj = find(j);
        if (v[ci] > v[cj]) {
            v[cj] += v[ci];
            v[ci] = cj;
        } else {
            v[ci] += v[cj];
            v[cj] = ci;
    }   }
};

Implementation with MF-sets by size and with path compression

TBD: Explain

class DisjointSets {

    vector<int> v;

    // find operation (with path compression)
    int find (int i) {
        if (v[i] < 0) return i;
        else return v[i] = find(v[i]);
    }

public:

    /* Creates n disjoint sets. */
    DisjointSets (int n)
    :   v(n, -1)
    {   }

    /* Finds the class of element i. */
    int operator[] (int i) {
        return find(i);
    }

    /* Merges the classes of elements i and j. */
    void merge (int i, int j) {
        int ci = find(i);
        int cj = find(j);
        if (v[ci] > v[cj]) {
            v[cj] += v[ci];
            v[ci] = cj;
        } else {
            v[ci] += v[cj];
            v[cj] = ci;
    }   }
};

Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2023