UVa 11503 - Virtual Friends

//aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

map<string, string> par;
map<string, int> cnt;

string findr(string s)
{
    if(par[s]=="") return s;

    string x = findr(par[s]);
    par[s] = x;
    return x;
}

int main()
{
    ll t,f;
    string sa, sb;
    scl(t);
    while(t--)
    {
        scl(f);
        while(f--)
        {
            cin>>sa>>sb;
            if(par[sa]=="" and !cnt[sa]) cnt[sa]=1;
            if(par[sb]=="" and !cnt[sb]) cnt[sb]=1;

            string u = findr(sa), v = findr(sb);

            if(u!=v)
            {

                par[v] = u;
                cnt[u] = cnt[u] + cnt[v];

            }
            printf("%d\n", cnt[u]);
        }
        par.clear();
        cnt.clear();
    }
    return 0;
}

/// my ideas (unsorted)


what did the problem want?

there're friends. betty's friend jessy, jessy's friend ketty.
there will be different inputs of two lines giving two connected frineds name .

at each query you have to tell that how many friends are there in that group?

what is the concept of disjoint set?

at first all nodes are their own parent. after that they get connected with one another. and at the time of
every connection the parent of the child nodes get changed .

now in this problem how can we apply that thing?

we have to count number of frineds in a grp;

so each time, we get two frinds and connect them eventually we have our grps increased. and then we have to
track that increase in an array or map.

how do this increase tracking work?

** firstly, all new friends who are not connected yet has member 1. and each time we make union between two
single node, then we get member in that group by adding both of the single node and we get 2.

-> where do we save this count? there are two nodes. in map of which node or both??
yupp, gotcha.. we save the count in ther counter map/array of the parent node.

** accordingly, now if we add another single node , with that grp of two nodes then what happens?

-> we increase the counter of connected nodes. where ? at the map of the parent node..!

** now if we add two nodes which comes from two different well formed grps then what happens?

-> we dont have any problem with the union part . just make union with the parent of those two different
grps. but counter?? now we just add the cnt of two parents and minus 2 from that.
now we get the new number of cnt from a single grp.

@@@ now technical facts... can you directly add two strings and make union with them without converting into
integer nodes. yes we can do so. okay. so no need to convert the strings.