UVA 11503 - Virtual Friends Solution

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

class DS{
private:
    vector<int>parent,rank,setSize;
    int numSets;
public:
    DS(int n)
    {
        numSets=n;
        parent.assign(n,0);
        rank.assign(n,0);
        setSize.assign(n,1);
        for (int i=0;i<n;i++) parent[i]=i;
    }
    int findParent(int i)
    {
        return parent[i]==i?i:parent[i]=findParent(parent[i]);
    }
    bool isSame(int i,int j) { return findParent(i)==findParent(j);}
    void unionSet(int x,int y)
    {
        int xRoot=findParent(x);
        int yRoot=findParent(y);
        if (xRoot==yRoot) return;
        if (rank[xRoot]>rank[yRoot])
        {
            setSize[xRoot]+=setSize[yRoot];
            parent[yRoot]=xRoot;
        }
        else
        {
            setSize[yRoot]+=setSize[xRoot];
            parent[xRoot]=yRoot;
            if (rank[xRoot]==rank[yRoot]) rank[yRoot]++;
        }
        numSets--;
    }
    int numDisjointSet(){ return numSets; }
    int SizeOfSet(int i) { return setSize[findParent(i)]; }
};
map<string,int>m;

int main()
{
    int testcases;
    scanf("%d",&testcases);
    while (testcases--)
    {
        int friendships;
        scanf("%d",&friendships);
        DS u(friendships*2);
        m.clear();
        string s1,s2;
        int indexing=0;
        while (friendships--)
        {
            cin>>s1>>s2;
            if (!m.count(s1)) m[s1]=indexing++;
            if (!m.count(s2)) m[s2]=indexing++;
            u.unionSet(m[s1],m[s2]);
            printf("%d\n",u.SizeOfSet(m[s1]));
        }
    }
    return 0;
}