2.Social Network Community

Spoj

You need to build an ADD friend feature. if 'x' sends a friend request to 'y', he may accept it or deny it.

SOCNET has a special feature called 'community'.When two people 'x' and 'y' becomes friends,the communities of two are merged together.(If 'x' has no friends, it's community consist of only himself)

Since, your friend is low on funds, the data center he uses has a restriction-the MAXIMUM size of any community cannot exceed 'm'.

You need to work on following three types of queries-

• A x y - x sends a friend request to y

• E x y - check whether x and y are present in same community(print 'Yes' or 'No')

• S x - prints the size of the community 'x' belongs to.

NOTE- A friend requested is accepted only if the merger of the two communities results in a community not greater than 'm'.

Solution : (Union using rank , path compression)

#include <bits/stdc++.h>

using namespace std;

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> &size, int a, int b, int maxS)
{
    int parA = findParent(v, a);
    int parB = findParent(v, b);

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1, -1);
    vector<int> r(n + 1, 0);
    vector<int> sz(n + 1, 1);

    int q;
    cin >> q;
    for (int k = 1; k <= q; k++)
    {
        char c;
        cin >> c;

        if (c == 'A')
        {
            int x, y;
            cin >> x >> y;
            uni(v, r, sz, x, y, m);
        }
        else if (c == 'E')
        {
            int a, b;
            cin >> a >> b;
            int parA = findParent(v, a);
            int parB = findParent(v, b);
            if (parA == parB)
            {
                cout << "Yes"
                     << "\n";
            }
            else
            {
                cout << "No"
                     << "\n";
            }
        }
        else if (c == 'S')
        {
            int w;
            cin >> w;
            int h = findParent(v, w);
            cout << sz[h] << "\n";
        }
    }
    return 0;
}

Time Complexity: O(n)