Disjoint-set data structure 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 &lt;cstdlib&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;

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-&gt;parent)
        root-&gt;parent = find(root-&gt;parent);
    return root-&gt;parent;
}

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

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

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

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

    cin &gt;&gt; n &gt;&gt; q;

    vector&lt;node*&gt; v (n); //vector holding all pointers to sets of nodes

    for (int i = 0; i &lt; n; i++) //make n sets of 1 element each
    {
        node* n = new node(i);
        n-&gt;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.
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&lt;node*&gt; 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&lt;node*&gt; &amp;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&lt;node*&gt; &amp;v)
{
    if (find(v.at(i - 1))-&gt;data == find(v.at(j - 1))-&gt;data)
        return 1;
    return 0;
}


to this:
bool sameSet(int i, int j, vector&lt;node*&gt; &amp;v)
{
    return find(v[i-1]) == find(v[j-1]);
}