Hackerrank Components In A Graph Solution

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
vector<int> p(30001),rnk(30001,1),num(30001,1);
bitset<30001> visit;
int n;
int find(int a){
    return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
    return find(a)==find(b);
}
void merge(int a,int b){
    if(!same(a,b)){
        if(rnk[find(a)]>rnk[find(b)]){
            num[find(a)]+=num[find(b)];
            p[find(b)]=find(a);
        }
        else {
            num[find(b)]+=num[find(a)];
            p[find(a)]=find(b);
        }
        if(rnk[find(a)]==rnk[find(b)])
            rnk[find(b)]++;
    }
}
int main(){
    for(int i=1;i<=30000;i++)
        p[i]=i;
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        merge(x,y);
    }
    int mx=1,mn=30000;
    for(int i=1;i<=n;i++){
        if(visit[find(i)])continue;
        visit[find(i)]=1;
        if(num[find(i)]>mx)mx=num[find(i)];
        if((num[find(i)]<mn)&&(num[find(i)]>1))mn=num[find(i)];
    }
    cout<<mn<<' '<<mx<<endl;
}

Comments