➤ Problem Link : 277A. Learning Languages
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int parent[101];
bool zero[101];
int find(int v)
{
if(parent[v]==v)
return v;
return parent[v]=find(parent[v]);
}
int main()
{
int n,m,a,b;
cin>>n>>m;
memset(zero,0,sizeof(zero));
unordered_map<int,vector<int> > mp;
for(int i=1;i<=n;i++)
parent[i]=i;
for(int i=1;i<=n;i++)
{
int c,lang;
cin>>c;
if(c==0)
zero[i]=1;
for(int j=0;j<c;j++)
{
cin>>lang;
for(int k=0;k<mp[lang].size();k++)
{
a=find(i);
b=find(mp[lang][k]);
if(a!=b)
parent[b]=a;
}
mp[lang].push_back(i);
}
}
int cnt=0;
int zct=0;
for(int i=1;i<=n;i++)
{
if(zero[i])
zct++;
else if(parent[i]==i)
cnt++;
}
if(cnt>0)
cout<<cnt-1+zct<<"\n";
else
cout<<zct<<"\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!!
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.