1.Implementation of union find

Implementing union and find

Union Find : ( O(n) )

int findParent(vector<int> v, int node)
{
    while (v[node] != -1)
    {
        node = v[node];
    }
    return node;
}

void uni(vector<int> &v, vector<int> &sz, int a, int b)
{

    int parA = findParent(v, a);
    int parB = findParent(v, b);

    if (parA != parB)
    {
        v[parA] = parB;
        sz[parB] = sz[parB] + sz[parA];
    }
    return;
}

Union using rank and Find using path compression : (O (log (n) ))

int findParent(vector<int> &v, int node)
{
    if (v[node] == -1)
    {
        return node;
    }

    v[node] = findParent(v, v[node]);
    return v[node];
}


void uni(vector<int> &v, vector<int> &r, vector<int> &sz, int a, int b)
{

    int parA = findParent(v, a);
    int parB = findParent(v, b);

    if (parA != parB)
    {
        if (r[parA] > r[parB])
        {
            v[parB] = parA;
            sz[parA] = sz[parA] + sz[parB];
        }
        else if (r[parB] > r[parA])
        {
            v[parA] = parB;
            sz[parB] = sz[parB] + sz[parA];
        }
        else
        {
            v[parA] = parB;
            sz[parB] = sz[parB] + sz[parA];
            r[parB]++;
        }
    }
    return;
}