Even Groups

TCS CodeVita 2014 Questions : Round1 (Set2)

Problem : Online Communities - Even Groups

In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input Format:

Input will consist of three parts, viz.

1. The total number of people on the social network (N)
2.Queries 

• C I J, connect I and J
• Q 0 0, print the number of communities with even member-count

-1 will represent end of input.

Output Format:

For each query Q, output the number of communities with even member-count

Constraints:

1<=N<=10^6

1<=I, J<=N

Sample Input and Output

SNo.	Input	Output
1	5 Q 0 0 C 1 2 Q 0 0 C 2 3 Q 0 0 C 4 5 Q 0 0 -1	0 1 0 1

Explanation:

For first query there are no members in any of the groups hence answer is 0.
After C 1 2, there is a group (let's take it as G1) with 1 and 2 as members hence total count at this moment is 1.
After C 2 3 total members in G1 will become {1, 2, 3} hence there are no groups with even count.
After C 4 5 there formed a new group G2 with {4, 5} as members, hence the total groups with even count is 1.

**************************EDITORIAL************************************************************

 we maintained a sets of all the community .. initially all the sets are disjoint soo no of comunity with even member count is initially zero .. now we follow a simple joining procedure based on the rank and parent of the current member .

suppose we join  set x and set y 

 case 1- if size of  size of  set x and size of set y are even then it will for a set with even size (since sum of two even is even )

             so the  no of set with even size decrease by 1 (since 2 even set form a single even  set)

case 2 - if the size of set x  is even ane of set y is odd ( or vice vaesa ) ,  no of set with even size agai decrease by 1 

 since even + odd =odd

case 3 - if size of set x and of y are odd tha no of set with even size increase by 1 

   since odd+odd=even 

now

  also while merging rank of bigger one set will be sum of rank of x and y 

************************CODE*******************************************

#include<iostream>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

int rank[100010];

int parent[100010];

long long int ans=0;

int find(int node)

{

     if(parent[node]==node)

     {

       return node;

     }

     else

     find(parent[node]);

}

int merge(int a, int  b)

{

  int x=find(a);

  int y=find(b);

  int f=0;

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

  {

  if(rank[x]%2==0 && rank[y]%2==0)// BOTH EVEN 

  {

  ans--;

  }

  else if(rank[x]%2!=0 && rank[y]%2!=0)// BOTH ODD

  {

  ans++;

 

  }

  else // ODD EVEN 

  ans--;

  rank[x]+=rank[y];

  parent[y]=x;

  }

  else

  {

  if(rank[x]%2==0 && rank[y]%2==0)

  {

  ans--;

  }

  else if(rank[x]%2!=0 && rank[y]%2!=0)

  {

  ans++;

  // cout<<"here "<<endl;

  }

  else 

  ans--;

  rank[y]+=rank[x];

  parent[x]=y;

  }

}

int main()

{

 int n;

 cin>>n;

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

 {

    parent[i]=i;

    rank[i]=1;

 }

while(1)

 {

 // ans=0;

  char arr[10];

   int a,b;

     cin>>arr;

     

       if(arr[0]=='-')

        {

        return 0;

        }

         else 

         {

       cin>>a>>b;

         if(a!=0)

         {

         

          if(find(a)!=find(b))// BOTH a AND b are not in the same set since if in same set thene no change in ans 

          {

          merge(a,b);

          }

         }

         else

          {

            cout<<ans<<endl;

          }

      }

 }

 return 0;

}