➤ Problem Link : LOSTNSURVIVED
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int par[100001];
set<pair<int,int> >size;
int sz[100001];
int find(int a)
{
if(par[a]==a)
return a;
return par[a]=find(par[a]);
}
int main()
{
int n,q,a,b;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
par[i]=i;
sz[i]=1;
size.insert(make_pair(1,i));
}
for(int i=1;i<=q;i++)
{
cin>>a>>b;
int p1=find(a);
int p2=find(b);
if(p1!=p2)
{
size.erase(make_pair(sz[p1],p1));
size.erase(make_pair(sz[p2],p2));
par[p2]=p1;
sz[p1]+=sz[p2];
size.insert(make_pair(sz[p1],p1));
}
auto l=size.begin();
auto s=--size.end();
cout<<(*s).first-(*l).first<<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!!
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.