2013年1月6日

UVa 11503 - Virtual Friends


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

map<string, string> p;
map<string, int> num;

string find(string x) {
  return x == p[x] ? x : (p[x] = find(p[x]));
}

void add(string a, string b) {
  string x = find(a), y = find(b);
  if (x == y) {
    printf("%d\n", num[y]);
    return;
  }
  num[y] += num[x];
  num[x] = 0;
  p[x] = y;
  printf("%d\n", num[y]);
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    p.clear();
    num.clear();
    int n;
    scanf("%d", &n);
    while (n--) {
      char a[30], b[30];
      scanf("%s%s", a, b);
      string s1 = string(a), s2 = string(b);
      if (!p.count(s1)) p[s1] = s1, num[s1] = 1;
      if (!p.count(s2)) p[s2] = s2, num[s2] = 1;
      add(s1, s2);
    }
  }
  return 0;
}

沒有留言:

張貼留言