My solution for uva11503

11503.cpp

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
#define fastio  do {std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);} while(0)
/************************/
/* VARIABLE DECLARATION */
/************************/
#define MAX 100005
int n;
vi P(MAX);
vi C(MAX, 1);
vi L(MAX, 0);

/*******************/
/* END DECLARATION */
/*******************/
int find_set(int u) {
  while (u != P[u]) {
    u = P[u];
  }

  return u;
}

void union_set(int u, int v) {
  int up = find_set(u);
  int vp = find_set(v);
  int child, parent;

  if (up == vp) return;

  if (L[up] >= L[vp]) {
    parent = up;
    child = vp;
  } else {
    parent = vp;
    child = up;
  }

  P[child] = parent;
  
  C[parent] += C[child];
  C[child] = C[parent];

  if (L[child] == L[parent]) L[parent]++;
}

int main()
{
  fastio;
  
  // Variables
  string f1, f2;
  map<string, int> M;
  int t, id;

  cin >> t;
  string outstr = "";
  while (t--) {
    // Input
    cin >> n;
    id = 0;

    for (int i = 0; i < MAX; i++) P[i] = i;
    for (int i = 0; i < MAX; i++) C[i] = 1;
    for (int i = 0; i < MAX; i++) L[i] = 0;
    M.clear();

    while (n--) {
      cin >> f1 >> f2;

      // Solve
      if (M.count(f1) == 0) M[f1] = id++;
      if (M.count(f2) == 0) M[f2] = id++;

      union_set(M[f1], M[f2]);

      // Output
      outstr += to_string (C[find_set(M[f1])]) + '\n';
    }
  }

  cout << outstr;

  return 0;
}