HackerEarth City and Campers problem solution

In this HackerEarth City and Campers problem-solution “Money money MONEY, I want money” thought Alex. “Now how do I get money? Well… I’ll open up a camp!”

Well, unfortunately, things didn’t go so well for Alex’s campers, and now there are N campers wandering around the city aimlessly. You have to handle Q queries; which consist of two groups finding each other and becoming one larger group. After each query, output the difference between the group of largest size and group of smallest size. If there is only one group, output 0. At first, everyone is in their own group.

Also note, if the two campers in the query are already in the same group, print the current answer, and skip merging the groups together.

HackerEarth City and Campers problem solution.

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
set <PII> keep;
int parent [100005]; 
int sz[100005]; 
int findset (int a)
{
    if(parent[a]==0)return a;return parent[a]=findset(parent[a]);
}
void merge (int a,int b)
{
    int k = findset(a), kk = findset(b); 
    if(k==kk)return;
    parent[k]=kk; 
    keep.erase(PII(sz[kk], kk));
    keep.erase(PII(sz[k], k));
    sz[kk]+=sz[k];
    keep.insert(PII(sz[kk],kk));
}
int main()
{
    ios_base::sync_with_stdio(0); 
    int N, Q; cin >> N >> Q;
    for (int g=1;g<=N;g++)keep.insert(PII(1, g)),sz[g]=1;
    for (int g=0; g<Q; g++)
    {
        int a, b; cin >> a >> b;
        merge(a, b); 
        set <PII> :: iterator ending = keep.end(); ending--; 
        set <PII> :: iterator beginning = keep.begin(); 
        cout << (*ending).first-(*beginning).first << 'n'; 
    }   
    return 0; 
}

Second solution

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5;
const int maxq = 1e5;
const int lim = 1e5 + 1;

struct cmp
{
    bool operator() (const pair<int, int>& a, const pair<int, int>& b)
    {
        return a.second < b.second;
    }
};

int n, q;
vector<int> parent(lim);
vector<int> size(lim);
multiset<pair<int, int>, cmp> S;

void init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        size[i] = 1;
        S.insert(make_pair(i, 1));
    }
}

int ancestor(int a)
{
    if (parent[a] != a)
        parent[a] = ancestor(parent[a]);
    return parent[a];
}

void merge(int a, int b)
{
    a = ancestor(a);
    b = ancestor(b);

    if (a == b)
        return;

    if (size[b] > size[a])
        swap(a, b);

    S.erase(S.find(make_pair(a, size[a])));
    S.erase(S.find(make_pair(b, size[b])));

    size[a] += size[b];
    parent[b] = a;

    S.insert(make_pair(a, size[a]));
}

int main()
{
    scanf("%d%d", &n, &q);

    assert(1 <= n and n <= maxn);
    assert(1 <= q and q <= maxq);

    init(n);

    for (int i = 0; i < q; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        assert(1 <= a and a <= n);
        assert(1 <= b and b <= n);

        merge(a, b);

        int large = (*(S.rbegin())).second;
        int small = (*(S.begin())).second;

        printf("%dn", large - small);
    }
    return 0;
}

coding problems solutions