FRNDCIRC - FRIEND CIRCLE - SOLUTION

FRNDCIRC - FRIEND CIRCLE is an easy DSU problem. If  DSU is an "alien" term for you, I recommend you to, understand Disjoint set union first and then try solving this problem!

If you want to solve easier problem based on DSU, try solving FOXLINGS. If you find difficulty in solving this problem you can refer to the tutorial.

In this problem, in each test case, we are given 'n' , number of  new friendships. For each such new forming friendship, we need to find the total number of people in their friend circle!

So, for each query, if the new friends were already in the same friend circle, their friendship will not affect the size of friend circle. But if they were not friends before, we will perform union operation on their friend circles, and the new size of friend circle will be, friend1_cirlce_size + friend2_cirlce_size.

I know, now you can code solution for this problem easily, isn't it?
More hint? You need to use STL (unordered_map) to solve this problem.

If you find any problem in solving this question, refer to the following code:

	#include "bits/stdc++.h"
	using namespace std;
	typedef unsigned long long ull;
	typedef long long int ll;
	typedef vector<long long int> vi;
	typedef pair<int, int> ii;
	typedef vector<ii> vii;
	std::unordered_map<std::string,std::string> visit;
	map<string,int> val;
	ll maxi=1,mini=1;
	ll co=0;
	string root(string x)
	{
	while(x!=visit[x])
	{
	visit[x]=visit[visit[x]];
	x=visit[x];
	}
	return x;
	}
	void unin(string a, string b)
	{
	visit[(b)]=(a);
	}
	int main()
	{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	ll t;
	cin>>t;
	while(t--)
	{
	ll n;
	cin>>n;
	visit.clear();
	val.clear();
	while(n--)
	{
	string a,b;
	cin>>a>>b;
	if(!val[a])
	val[a]=1,visit[a]=a;
	if(!val[b])
	val[b]=1,visit[b]=b;
	string ra,rb;
	ra=root(a);
	rb=root(b);
	if(ra!=rb)
	{
	unin(ra,rb);
	val[ra]=val[ra]+val[rb];
	}
	cout<<val[ra]<<endl;
	}
	}
	return 0;
	}

view raw FRNDCIRC.cpp hosted with ❤ by GitHub