We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<cmath>#include<cstdio>#include<vector>#include<iostream>#include<algorithm>usingnamespacestd;intfindset(intx,vector<int>&r){// we compress path here tooif(r[x]!=x)r[x]=findset(r[x],r);return(r[x]);}intmain(){intn,q;cin>>n>>q;// makesetvector<int>root(n+1);vector<int>count(n+1);for(inti=1;i<=n;i++){root[i]=i;count[i]=1;}while(q--){chart;cin>>t;if(t=='M'){intx,y;cin>>x>>y;// find root of x & yintrx=findset(x,root);intry=findset(y,root);// skip, already in same communityif(rx==ry)continue;// do a union not using ranking root[rx]=ry;count[ry]+=count[rx];count[rx]=0;}elseif(t=='Q'){intp;cin>>p;cout<<count[findset(p,root)]<<endl;}}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merging Communities
You are viewing a single comment's thread. Return to all comments →
C++, passed all tests: