217A. Ice Skating - Codeforces Solution C++

➤  Problem Link : 217A. Ice Skating 

✅ C++ Solution :

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

int parent[101];

int find(int v)
{
	if(parent[v]==v)
		return v;

	return parent[v]=find(parent[v]);

} 

int main()
{
	int n;
	cin>>n;

	for(int i=1;i<=n;i++)
		parent[i]=i;

	unordered_map<int,vector<int> > xmp,ymp;
	int x,y;
	int a,b;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		for(int j=0;j<xmp[x].size();j++)
		{
			a=find(i);
			b=find(xmp[x][j]);

			if(a != b)
				parent[a]=b;

		}

		for(int j=0;j<ymp[y].size();j++)
		{
			a=find(i);
			b=find(ymp[y][j]);

			if(a != b)
				parent[a]=b;
		}

		xmp[x].push_back(i);
		ymp[y].push_back(i);
	}

	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(parent[i]==i)
			ans++;
	}

	cout<<ans-1<<"\n";


}

 

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!!

• Tweet
• Share
• Share
• Share
• Share

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.