Union Find Appln For finding disconnected group with max no of nodes inside

Problem :- https://www.hackerrank.com/challenges/kundu-and-tree

Edotorial :  https://www.hackerrank.com/challenges/kundu-and-tree/editorial


In this question, Rank will store the Number of nodes under it's Group. So, Obviously ,in the beginning Rank will be one (Represent single member ).




#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int abcd[100010];
int parent[100010];
typedef long long int lli;
#define mod 1000000007
long long int B[100009],C[100009],D[100009];
#define MOD 1000000007


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;
 
  }
  else
  {
       parent[x]=y;
       abcd[y]+=abcd[x];
       abcd[x]=0;        
  }
}


int main()
{
 int n;
 cin>>n;

 for(int i=0;i<=n+1;i++)
 {
    parent[i]=i;
    abcd[i]=1;
 }

 for(int i=0;i<n-1;i++)
 {
     int  a,b;
char c;
cin>>a>>b>>c;

 if(c=='r') continue;
 else
 {
  if(find(a)!=find(b))
   {
    merge(a,b);
                   }
 }
 }


  vector<lli>count1;
  for(int i=0;i<=n;i++) count1.push_back(0);
  for(int i=1;i<=n;i++)
   {
    if(abcd[i]!=0)
     {
      count1[i]=(abcd[i]);// size of all  sets
      }
   }


**********By the below Method we converted the complexity of O(n^3) to O(n)************

//*/**** jadu way to calculate product of all possible triplets in 4*o(n)*/

   B[n-1] = count1[n];
    int i;
    for(i=n-2;i>=0;i--) B[i] = (B[i+1] + count1[i+1])%MOD;

    for(i=1;i<n-1;i++) C[i] = (count1[i+1]*B[i+1])%MOD;

    D[n-2] = C[n-2];
    for(i=n-3;i>=1;i--) D[i] = (D[i+1] + C[i])%MOD;
lli sum=0;
    for(i=0;i<n-2;i++) sum = (sum + count1[i+1]*D[i+1])%MOD;
    cout<< ( MOD + sum )%MOD<<endl;
    /*** jadu end*/////////////
 return 0;
}