Disjoint-set data structure

Question

I'm trying to speed up my union-find disjoint set data structure. The idea is that initially n sets of single element sets are made, and put into a vector nodes. Each node has a parent node, and the highest parent of any particular index in the vector is the highest ranking member of set. Two concepts, union by rank and path compression, are used to achieve faster merging and finding times.

There are two querying types: Union of two values (and thus their sets), and checking if 2 members are in the same set.

Nevertheless, when using very large values for n (such as 100,000,000) and and m (such as 1,000,000), the program takes a bit of time to run. Generally around 30 seconds for my machine.

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>

using namespace std;


int n; //number of total elements
int q; //number of queries

struct node
{
    int data;
    node* parent;
    int rank;
    node(int d);
};

node::node(int d)
{
    data = d;
    rank = 0;
    parent = nullptr;
}

node* find(node* root)
{
    if (root != root->parent)
        root->parent = find(root->parent);
    return root->parent;
}

void merge(node* one, node* two)
{
    node* i = find(one);
    node* j = find(two);
    if (i->rank > j->rank)
        j->parent = i;
    else
        i->parent = j;

    if (i->rank == j->rank)
    {
        i->parent = j;
        j->rank++;
    }
}

int sameSet(int i, int j, vector<node*> v)
{
    if (find(v.at(i - 1))->data == find(v.at(j - 1))->data)
        return 1;
    return 0;
}

int main(int argc, char** argv) {

    cin >> n >> q;

    vector<node*> v (n); //vector holding all pointers to sets of nodes

    for (int i = 0; i < n; i++) //make n sets of 1 element each
    {
        node* n = new node(i);
        n->parent = n;
        v[i] = n;
    }
}

Would using a map instead of a vector, for example, be faster? Am I not compressing the path correctly (so that every member of a sets immediate parent is the highest ranking member) or unionizing by rank? As far as I'm aware, both merge and find should take O(log n) if implemented in the most efficient way, making me think this should be faster than it is.

Answer 1

Copying a huge vector by mistake

The reason your program is so slow is because of this line:

int sameSet(int i, int j, vector<node*> v)

This function makes a copy of the vector every time you want to do a simple check on two nodes. If you simply change that line to this:

int sameSet(int i, int j, vector<node*> &v)

then your program will avoid the copy. In my testing, the program ran in 1-2 seconds instead of over a minute with a large n.

Also, that function could be simplified from this:

int sameSet(int i, int j, vector<node*> &v)
{
    if (find(v.at(i - 1))->data == find(v.at(j - 1))->data)
        return 1;
    return 0;
}

to this:

bool sameSet(int i, int j, vector<node*> &v)
{
    return find(v[i-1]) == find(v[j-1]);
}

Answer 2

So first things first:

Dont use namespace std; It is a bad practice and generally unneeded;

There are some lets say odd things about your code. First thing it feels a lot like some basic C-code rather than C++. On top of that you deviate from standard practices. For example you use recursive function calls to find the parent:

node* find(node* root)
{
    if (root != root->parent)
        root->parent = find(root->parent);
    return root->parent;
}

The more idiomatic version would be a while loop:

node* find(node* root)
{
    while (root != root->parent) {
        root->parent = root->parent->parent;
    }
    return root->parent;
}

However, this function does something really terrible, as it overwrites the parent member of node and all its parents, which is most certainly not what the user expects of a function called "find". So you should rather add a temporary for that

node* find(node* root)
{
    node* temp = root->parent;
    while (temp != root) {
        temp = temp->parent;
    }
    return temp;
}

---

In your merge function you have an overlap, as i->parent = j; Is set twice. Once in the first else for !(i->rank > j->rank) and once in the second. For clarity i would suggest to use an else if

void merge(node* one, node* two)
{
    node* i = find(one);
    node* j = find(two);
    if (i->rank > j->rank) {
        j->parent = i;
    } 
    else if (i->rank == j->rank)
    {
        i->parent = j;
        j->rank++;
    }
    else {
        i->parent = j;
    }
}

---

Memory management

You are currently leaking nearly all of the memory allocated in you program. Every node is allocated by a call to new

node* n = new node(i);

However, there is no call to delete that i can see. The C-way would be to cleanup at the end of your main function. However in C++ we have smart pointer, that handle this for you. So rather than simply calling new you can use a std::unique_ptr. While we are at it, you can combine the constructor call with the insertion into you vector and reserve the memory beforehand

std::vector<std::unique_ptr<node>> v;
v.reserve(n);
for (int i = 0; i < n; i++) //make n sets of 1 element each
{
    v[i].emplace_back(std::make_unique<node>(i));
    n->parent = n;
}

---

What is also apparent is that you are setting n->parent = n whenever you construct the element, so maybe just add it to the constructor?