[UVa] 11503 Virtual Friends.cpp

#include <iostream>
#include <map>
#include <string>
using namespace std;

int Set[200010];
int Num[200010];

void Set_Initial(int N);
int FindRoot(int x);
void Union(int x, int y);

int main()
{
    ios::sync_with_stdio(false);
    int Case, F;
    cin >> Case;
    while (Case--) {
        cin >> F;
        map<string, int> Map;
        Set_Initial(2 * F);

        string A, B;
        for (int i = 0, j = 1; i < F; ++i) {
            cin >> A >> B;
            if (!Map[A]) Map[A] = j++;
            if (!Map[B]) Map[B] = j++;
            Union(Map[A], Map[B]);
        }
    }
}
void Set_Initial(int N)
{
    for (int i = 0; i <= N; ++i) {
        Set[i] = i;
        Num[i] = 1;
    }
}
int FindRoot(int x)
{
    if (x == Set[x])
        return x;
    return Set[x] = FindRoot(Set[x]);
}
void Union(int x, int y)
{
    x = FindRoot(x);
    y = FindRoot(y);

    if (x != y) {
        Set[x] = y;
        Num[y] += Num[x];
    }
    cout << Num[y] << endl;
}