Components in a graph(FIND MAXIMUM AND MINIMUM SIZE OF SET FORMED )

Components in a graph

https://www.hackerrank.com/challenges/components-in-graph

<FIND MAXIMUM AND MINIMUM SIZE OF SET FORMED >

Problem Statement

There are 2N values to represent nodes in a graph. They are divided into two sets G and B. Each set has exactly N values. Set G is represent by {G1,G2,⋯,GN}. G can take any value between 1 to N(inclusive). Set B is represented by {B1,B2,⋯,BN}. B can take any value between N+1 to 2N(inclusive). Same value can be chosen any number of times.

Here (G1,B1),(G2,B2),⋯(GN,BN) represents the edges of the graph.

Your task is to print the number of vertices in the smallest and the largest connected components of the graph.

For more clarity look at the following figure.

For the above graph smallest connected component is 7 and largest connected component is 17.

Input Format

First line contains an integer N. 
Each of the next N lines contain two space-separated integers, ith line contains Gi and Bi.

Constraints 
1≤N≤15000 
1≤Gi≤N 
N+1≤Bi≤2N

Output Format

Print two space separated integers, the number of vertices in the smallest and the largest components.

Sample Input

5
1 6 
2 7
3 8
4 9
2 6

Sample Output

2 4

Explanation

The number of vertices in the smallest connected component in the graph is 2 i.e. either (3,8) or (4,9). 
The number of vertices in the largest connected component in the graph is 4 i.e. 1−2−6−7.

---------------------------------------code----------------------------------------------------------------------------------------

IN THIS PROBLEM WE NEED TO SIMPLY FIND MINIMIM AND MAXIMUM SIZE OF SET FORMED FROM THE GIVEN SET OF  EDGES

..

FOR THIS PROBLEM WE MANUPULATE RANK[], WILE MERGING TWO SET ONLY PARENT OF THAT SET WILL CONTAIN SIZE OF THAT SET AND REST ALL VERTEX WILL CONTAINS 0.

SO WHILE MERGING LET X WILL BE PARENT OF Y THAN 

PAR[Y]=X; RANK[X]+=RANK[Y], RANK[Y]=0;

INITIALLY RANK OF ALL VERTEX IS 1..

--------------------------------------------------CODE-----------------------------------------------------------------------------------

.#include<iostream>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

int abcd[100010];

int parent[100010];

int find(int node)

{

int k;

     if(parent[node]==node)

     {

       return node;

     }

     else

    k=  find(parent[node]);

   return k;

     

}

void  merge(int a, int  b)

{

  int x=find(a);

  int y=find(b);

  if(abcd[x]>abcd[y])

  {

   

      parent[y]=x;

      abcd[x]+=abcd[y];

  abcd[y]=0;

  //cout<<" merging "<<a<<" b "<<b<<"  as a common parent "<<x<<" abcd y "<<abcd[y]<<" abcd x "<<abcd[x]<<endl;

   

  }

  else

  {

      parent[x]=y;

   

   abcd[y]+=abcd[x];

  abcd[x]=0;

  //cout<<" merging "<<a<<" b "<<b<<"  as a common parent "<<y<<" abcd y "<<abcd[y]<<" abcd x "<<abcd[x]<<endl;

  }

}

int main()

{

 int n;

 cin>>n;

 int m;

m=n;

 vector<pair<pair<int ,int >,int> > v;

 int a , b,c;

 for(int i=0;i<m;i++)

 {

  cin>>a>>b;

  abcd[a]=1;

  abcd[b]=1;

  v.push_back(make_pair(make_pair(c,a),b) );

 }

 for(int i=1;i<=2*n+1;i++)

 {

    parent[i]=i;

    if(abcd[i]!=1) abcd[i]=-1;

 }

 sort(v.begin(),v.end());

 long long int cost=0;

 for(int i=0;i<m;i++)

 {

        a=v[i].first.second;

        b=v[i].second;

        // cout<<" taka "<<a<<" "<<b<<endl;

       if(find(a)!=find(b))

       {

          merge(a,b);

                

       }

 }

  int maxi=-1;

  int mini=10000000;

 for(int i=0;i<2*n+10;i++)

  {

  if(abcd[i]>maxi) maxi=abcd[i];

  if(abcd[i]<mini && abcd[i]!=-1 && abcd[i]!=0) mini=abcd[i];

  }

  cout<<mini<<" "<<maxi<<endl;

 return 0;

}