FRIENDS AND FOES

• Problem Description

  
  Monk will be organising a party as he recently got a promotion. He wants to invite his childhood classmates. Monk had a total of N classmates and a lot of them were friends with each other. There used to be M1 friendship relations. However, time took its toll and some of them became enemies. A total of M2
  
  enemy relations are formed.
  
  To avoid any nuisance in his party, Monk wants to invite only Special group of classmates in his party. Special group is the one where each person in the group is a friend of another and there should not be any two persons in that group who are enemies of each other. Now given the relationships among some of them, your task is to find the maximum number of classmates Monk can invite to his party.
  
  Note:
  
  1) Group of friends will be formed only by the given inputs. If given, A
  is a friend of B, B is a friend of C, then A,B,C
  
  forms a friendship group, and you cannot pick a subgroup from it.
  
  2) Two people are said to be friends of each other if their friend relation is given or they are connected through a chain of mutual friends. For example, if given A
  is a friend of B, and B is a friend of C then A and C
  
  are friends.
  
  3) Two people are said to be enemies of each other, only and only if their enemy relation is given. For example, if given A
  is a enemy of B, and B is a enemy of C, then A and C
  
  are not enemies of each other, unless it is given in the input.
  
  4) There wont be any case, where both friend and enemy relation is given for two people.
  
  Input:
  The first line consists of integer N
  , denoting the number of Monks classmates.
  The second line consists of integer M1 denoting the number of pair of friends.
  The next M1 lines consists of two integers of the form A and B who are friends with each other.
  The next line consists of integer M2 denoting the number of pair of enemies. The next M2 lines consists of two integers of the form A and B
  
  who are enemies.
  
  Output:
  Print in a single line, the maximum number of friends Monk can invite to his party provided they should form a Special group.
  
  Constraints:
  1<=N<=105
  
  1<=M1+M2<=min(2105,N(N1)/2)
  1<=A,B<=N
  
  

• CODING RENA::

• #include <stdio.h>

   

  int root(int a[],int i){

      while(a[i]!=i){

          a[i] = a[a[i]];

          i = a[i];

      }

      return i;

  }

   

  void Union(int a[],int size[],int A,int B){

      int rootA = root(a,A);

      int rootB = root(a,B);

      

      if(rootA == rootB) return;

      if(size[rootA] > size[rootB]){

          a[rootB] = a[rootA];

          size[rootA] += size[rootB];

      } else {

          a[rootA] = a[rootB];

          size[rootB] += size[rootA];

      }

  }

   

  void init(int a[], int size[], int n){

      int i;

      for(i=0; i<n; i++){

          a[i]=i;

          size[i]=1;

      }

  }

  int main(){

      int n,m1,m2;

      scanf("%d",&n);

      scanf("%d",&m1);

      int a[100001],size[100001];

      init(a,size,n);

      int i,x,y;

      for(i=0; i<m1; i++){

          scanf("%d %d",&x,&y);

          Union(a,size,x-1,y-1);

      }

      scanf("%d",&m2);

      for(i=0; i<m2; i++){

          scanf("%d %d",&x,&y);

          int rootX = root(a,x-1);

          int rootY = root(a,y-1);

          if(rootX == rootY) {

              size[rootX] = 0;

          }

      }

      int sum = 0;

      for(i=0; i<n; i++){

          int r = root(a,i);

          sum = (sum>size[r]?sum:size[r]);

          //size[a[i]] = 0;

      }

      printf("%d",sum);

      return 0;

  }

• Test Case 1

  
  Input (stdin)

  5
  
  3
  
  1 2
  
  1 3
  
  4 5
  
  2
  
  2 3
  
  2 4
  
  

  Expected Output

  2

• Test Case 2

  
  Input (stdin)

  4
  
  2
  
  1 2
  
  2 3
  
  2
  
  2 3
  
  1 3
  
  

  Expected Output

  1