2013年1月3日

UVa 115 - Climbing Trees


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

map<string, set<string> > parent, child;
set<string> check;
bool found;

void find(string a, string b, string path) {
  if (found) return;
  if (a == b) {
    int plus = 0, minus = 0;
    for (int i = 0; path[i]; i++)
      if (path[i] == '+') plus++;
      else minus++;
    if (plus && !minus) {
      while (plus-- > 2) printf("great ");
      while (plus--) printf("grand ");
      puts("child");
    } else if (minus && !plus) {
      while (minus-- > 2) printf("great ");
      while (minus--) printf("grand ");
      puts("parent");
    } else if (plus == 1 && minus == plus) {
      puts("sibling");
    } else {
      plus--;
      minus--;
      int min = plus < minus ? plus : minus;
      if (plus != minus) printf("%d cousin removed %d\n", min, plus > minus ? plus - minus : minus - plus);
      else printf("%d cousin\n", min);
    }
    found = 1;
    return;
  }
  check.insert(a);
  set<string>::iterator it;
  for (it = parent[a].begin(); it != parent[a].end(); it++)
    if (!check.count(*it)) {
      string next = path;
      next.insert(next.end(), '-');
      find(*it, b, next);
    }
  for (it = child[a].begin(); it != child[a].end(); it++)
    if (!check.count(*it)) {
      string next = path;
      next.insert(next.end(), '+');
      find(*it, b, next);
    }
}

int main() {
  string a, b;
  while (cin >> a >> b) {
    if (!a.compare("no.child")) break;
    child[a].insert(b);
    parent[b].insert(a);
  }
  while (cin >> a >> b) {
    check.erase(check.begin(), check.end());
    found = 0;
    if (a.compare(b)) find(a, b, "");
    if (!found) puts("no relation");
  }
  return 0;
}

沒有留言:

張貼留言