Merging Communities(count maximum size of set)

Merging Communities

https://www.hackerrank.com/challenges/merging-communities

similar to 

https://www.hackerrank.com/challenges/components-in-graph(for editorial  go to this question )

Problem Statement

People connect with each other in a social network. A connection between Person I and Person J is represented as M I J. When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to.

At the beginning, there are N people representing N communities. Suppose person 1 and 2connected and later 2 and 3 connected, then 1,2, and 3 will belong to the same community.

There are two type of queries:

1. M I J⟹ communities containing person I and J merged (if they belong to different communities).
2. Q I⟹ print the size of the community to which person I belongs.

Input Format

The first line of input will contain integers N and Q, i.e. the number of people and the number of queries.
The next Q lines will contain the queries.

Constraints :
1≤N≤105
1≤Q≤2×105

Output Format

The output of the queries.

Sample Input

3 6
Q 1
M 1 2
Q 2
M 2 3
Q 3
Q 2

Sample Output

1
2
3
3

Explanation

Initial size of each of the community 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;

cin>>m;

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

 int a , b,c;

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

 {

    parent[i]=i;

   abcd[i]=1;

 }

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

 {

  char d;

  cin>>d;

   if(d=='M')

    {

    cin>>a>>b;

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

       {

          merge(a,b);

                

       }

}

else

{

cin>>a;

int x=find(a);

cout<<abcd[x]<<endl;

}

 

 }

 return 0;

}