Disjoint-set data structure
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]);
}