731C. Socks - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 731C. Socks

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
ll parent[2*100001];
ll color[2*100001];
ll size[2*100001];
 
ll test(ll v)
{
  if(parent[v]==v)
    return v;
 
  return parent[v]=test(parent[v]);
 
}
 
int main()
{
  ll n,m,k,l,r,p1,p2;
  cin>>n>>m>>k;
    
 
    for(ll i=1;i<=n;i++)
    {
      cin>>color[i];
      parent[i]=i;
      size[i]=1;
    }
 
    for(ll i=1;i<=m;i++)
    {
      cin>>l>>r;
      p1 = test(l);
      p2 = test(r);
      if(p1!=p2)
      {
        parent[p2]=p1;
        size[p1]+=size[p2];
      }
    }
 
    map<ll,unordered_map<ll,ll> > mp;
 
    for(ll i=1;i<=n;i++)
    {
        //  cout<<i<<" "<<parent[i]<<endl;
        parent[i]=test(i);
      mp[parent[i]][color[i]]++;
    }
 
    int ans=0;
    for(auto it = mp.begin();it!=mp.end();it++)
    {
      ll maxi = -1;
      for(auto it2=(*it).second.begin();it2!=(*it).second.end();it2++)
        if((*it2).second > maxi)
          maxi = (*it2).second;
    //  cout<<size[(*it).first]<<" "<<maxi<<endl;
      ans+=size[(*it).first]-maxi;  
    }
 
 
    cout<<ans;
 
}

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.