UVa 11503 Virtual Friends

Problem Link: Click Here

Required Algorithm: Disjoint Set Union (Bangla)

Source Code in C++:

#include<bits/stdc++.h>
#define lli long long int
#define scf(n) scanf("%lld",&n)
#define prf(n) printf("%lld",n)
#define nl printf("\n")
#define spc printf(" ")
#define file freopen("in.txt","rt",stdin)
#define pii pair<int,int>
using namespace std;
map<string , lli > cnt_par;
map<string , string > par;
map<string,lli>check;


string find_func(string n)
{
    if(par[n]==n)
        return n;

    par[n] = find_func(par[n]);

    return par[n];

}

string union_func(string a,string b)/** a er parent b **/
{
    string u = find_func(a);
    string v = find_func(b);
    if(u!=v)
    {
        par[u] = v;
        cnt_par[v]+=cnt_par[u];
    }
    return v;
}


int main()
{

    //file;
    string str,str1;
    lli n,m,test,a,b;
    scf(test);
    while(test--)
    {
        scf(n);

        map<string,lli>check;
        lli mx = -1;
        for(int i=1; i<=n; i++)
        {
            cin>>str>>str1;

            if(check[str]==0)
            {
                check[str] = 1;
                par[str] = str;
                cnt_par[str] = 1;
            }
            if(check[str1]==0)
            {
                check[str1] = 1;
                par[str1]  = str1;
                cnt_par[str1] = 1;

            }
            string ans = union_func(str,str1);
            prf(cnt_par[ans]);
            nl;

        }
    }
    return 0;

}