Union-Find is used for make group or to find the different number of group or to find the max member of a group or to determine two things are in same or different group.

long Parent(long h1)
{
if(P[h1]==-1)
return h1;
P[h1] = Parent(P[h1]);
return P[h1];
}

for(i=1;i<=n;i++) // n number of thing
P[i]=-1;

for(i=1;i<=m;i++) // m number of connection
{
scanf(“%ld %ld”,&x,&y);
x1 = Parent(x);
y1 = Parent(y);
if(x1!=y1)
P[x1]=y1;
}

Maximum members of a group

for(i=1;i<=n;i++)
count[i]=0;

for(i=1;i<=n;i++)
count[Parent(i)]++;

max = 0;

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

if(count[i]>max)
max = count[i];

printf(“%ld\n”,max);

To find, any two members are same or different group

for(i=1;i<=k;i++)
{
scanf(“%ld %ld”,&x,&y);
x1 = Parent(x);
y1 = Parent(y);
if(x1!=y1)
printf(“Different\n”);
else
printf(“Same\n”);
}

Advertisements