UVA 10608 - Friends(cpp file)

Problem Type : Disjoint Set Data-Structure




#include<bits/stdc++.h>
#define MAX 500000
#define MAX1 30000
using namespace std;
long par[MAX1];
long n,m,color[MAX1];
void make_set()
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n1)
{
    if(par[n1]!=n1)
    {
        par[n1]=find_set(par[n1]);
    }
    return par[n1]=par[n1];
}
void Union(long p,long q)
{
    long ux = find_set(p);
    long uy = find_set(q);
    if(ux!=uy)
    {
        par[ux]=uy;
    }
}
int main()
{
    long test,i,j,v,e,store[MAX1],sum;
    scanf("%ld",&test);
    while(test--)
    {
        scanf("%ld %ld",&n,&m);
        make_set();
        for(i=1; i<=m; i++)
        {
            scanf("%ld %ld",&v,&e);
            Union(v,e);
        }
        store[0]=0;
        for(i=1; i<=n; i++)
        {
         long   ux=find_set(i);
            store[i]=ux;
        }
        sort(store,store+n+1);
        long  c=0,sum=0;
        for(i=1; i<n; i++)
        {
            c=0;
            for(j=i+1; j<=n; j++)
            {
                if(store[i]==store[j])
                {
                    c++;
                }
                else
                   break;
            }
            i=j-1;
            if(sum<c)
            {
                sum=c+1;
            }
        }
        printf("%ld\n",sum);
    }
}