2012年11月27日

UVa 599 - The Forrest for the Trees


#include <stdio.h>

int i, num[26], team[26];

void u(int a, int b) {
  int t1 = team[a], t2 = team[b];
  for (i = 0; i < 26; i++)
    if (team[i] == t2) num[t1]++, num[t2]--, team[i] = t1;
}

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  while (n--) {
    char s[200] = {};
    for (i = 0; i < 26; i++)
      num[i] = 1, team[i] = i;
    while (gets(s) && s[0] != '*')
      u(s[1] - 'A', s[3] - 'A');
    char t[200] = {};
    gets(t);
    int check[26] = {}, tree = 0, acorn = 0;
    for (i = 0; t[i]; i += 2) {
      int now = team[t[i] - 'A'];
      if (!check[now]) {
        check[now] = 1;
        if (num[now] == 1) acorn++;
        else tree++;
      }
    }
    printf("There are %d tree(s) and %d acorn(s).\n", tree, acorn);
  }
  return 0;
}

沒有留言:

張貼留言