Friend Circle Queries - Hacker Rank Solution

 The population of HackerWorld is . Initially, none of the people are friends with each other. In order to start a friendship, two persons  and  have to shake hands, where . The friendship relation is transitive, that is if  and  shake hands with each other,  and friends of  become friends with  and friends of .

You will be given  queries. After each query, you need to report the size of the largest friend circle (the largest group of friends) formed after considering that query.

Friend Circle Queries - Hacker Rank Solution

#include<bits/stdc++.h>
using namespace std;

const int MAX=500005;

int a[MAX], s[MAX];
set<int> sz;

void init(int n)
{
	for(int i=0;i<n;i++)
	{
		a[i]=i;
		s[i]=1;
	}
}

int root(int x)
{
	while(a[x]!=x)
	{
		a[x]=a[a[x]];
		x=a[x];
	}
	return x;
}

void join(int x,int y)
{
	int rx=root(x);
	int ry=root(y);
	if(rx==ry)
		return;
	if(s[rx]>s[ry])
	{
		s[rx]+=s[ry];
		a[ry]=rx;
		sz.insert(-s[rx]);
	}
	else
	{
		s[ry]+=s[rx];
		a[rx]=ry;
		sz.insert(-s[ry]);
	}
}

int main()
{
	int q;
	vector<pair<int,int> > queries;
	map<int,int> m;
	vector<int> aux;

	scanf("%d",&q);
	
	for(int i=0;i<q;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		queries.push_back(make_pair(x,y));
		aux.push_back(x);
		aux.push_back(y);
	}
	sort(aux.begin(),aux.end());
	int curr=1;
	for(int i=0;i<aux.size();i++)
	{
		if(i==0||aux[i]!=aux[i-1])
		{
			m[aux[i]]=curr++;
		}
	}
	for(int i=0;i<q;i++)
	{
		queries[i].first=m[queries[i].first];
		queries[i].second=m[queries[i].second];
	}

	init(curr);

	for(int i=0;i<q;i++)
	{
		join(queries[i].first,queries[i].second);
		printf("%d\n",-*(sz.begin()));
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

map<int,int> m,size;

// Complete the solve function below.

int root (int i)
{
    while(m[i] != i)
    {
        m[i] = m[m[i]]; 
        i = m[i]; 
    }
    return i;
}

int weighted_uni(int A,int B)
{
    int root_A = root(A);
    int root_B = root(B);
    if(root_A==root_B) return 0;
    if(size[root_A] < size[root_B])
    {
        m[root_A] = m[root_B];
        size[root_B] += size[root_A];
        return size[root_B];
    }
    else
    {
        m[root_B] = m[root_A];
        size[root_A] += size[root_B];
        return size[root_A];
    }
}

vector<int> solve(vector<int> L, vector<int> R) {

    assert(L.size() == R.size());
    
    int ans=1;
    
    vector<int> v;
    for(int i=0;i<L.size();++i)
    {
        if(!m.count(L[i]))
            m[L[i]]=L[i],size[L[i]]=1;
        if(!m.count(R[i]))
            m[R[i]]=R[i],size[R[i]]=1;
        
        ans=max(ans, weighted_uni(L[i],R[i]));
        v.push_back(ans);
    }
    return v;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    string L_temp_temp;
    getline(cin, L_temp_temp);

    vector<string> L_temp = split_string(L_temp_temp);

    vector<int> L(q);

    for (int i = 0; i < q; i++) {
        int L_item = stoi(L_temp[i]);

        L[i] = L_item;
    }

    string R_temp_temp;
    getline(cin, R_temp_temp);

    vector<string> R_temp = split_string(R_temp_temp);

    vector<int> R(q);

    for (int i = 0; i < q; i++) {
        int R_item = stoi(R_temp[i]);

        R[i] = R_item;
    }

    vector<int> ans = solve(L, R);

    for (int i = 0; i < ans.size(); i++) {
        fout << ans[i];

        if (i != ans.size() - 1) {
            fout << "\n";
        }
    }

    fout << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}