FRNDCIRC - FRIEND CIRCLE - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : FRNDCIRC

👉 Hint : edit please

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,string>par;
unordered_map<string,int>size;

string find(string i)
{
	if(par.find(i)==par.end())
		return i;
	return par[i]=find(par[i]);
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
	    par.clear();
	    size.clear();
		int n;
		string x,y;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>x>>y;
			string p1=find(x);
			string p2=find(y);
			if(p1==x && size.find(p1)==size.end())
				size[p1]=1;
			if(p2==y && size.find(p2)==size.end())
				size[p2]=1;	
			if(p1!=p2)
			{
				par[p1]=p2;
				size[p2]+=size[p1];
			}
			cout<<size[p2]<<endl;
		}
	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.