Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Climbing Trees

115.c

#include <stdio.h>
#include <stdlib.h>

char names[300][32];

int num_people=0;
struct {
	char name[32];
	int visited;
	int parent;
	int num_children;
	int * children;
} people[300];

int tree_len=0;
int tree[300];			/* 1:up, 2:down */

int
recorre_tree(int a,int b)
{
	int i;

	if (a==b) {
		return 1;
	}
	if (people[a].visited) {
		return 0;
	}
	people[a].visited=1;
	tree_len++;
	if (people[a].parent != -1) {
		tree[tree_len-1]=1;
		if (recorre_tree(people[a].parent, b)) {
			return 1;
		}
	}
	tree[tree_len-1]=2;
	for(i=0; i<people[a].num_children; i++) {
		if (recorre_tree(people[a].children[i], b)) {
			return 1;
		}
	}
	tree_len--;
	return 0;
}

#define ABS(a) ((a)>0 ? (a) : -(a))
#define MIN(a,b) ((a)<(b) ? (a) : (b))

void
calc(char * str1, char * str2)
{
	int a,b;
	int i;
	int num_up, num_down;

	for(a=0; a<num_people; a++) {
		if (!strcmp(str1, people[a].name)) {
			break;
		}
	}
	if (a>=num_people) {
		printf("no relation\n");
		return;
	}
	for(b=0; b<num_people; b++) {
		if (!strcmp(str2, people[b].name)) {
			break;
		}
	}
	if (b>=num_people) {
		printf("no relation\n");
		return;
	}
	for(i=0; i<num_people; i++) {
		people[i].visited=0;
	}
	tree_len=0;
	if (!recorre_tree(a,b)) {
		printf("no relation\n");
		return;
	}
	if (tree_len==0) {
		printf("same person?\n");
		return;
	}
	num_up = num_down=0;
	for(i=0; i<tree_len; i++) {
		if (tree[i]==1) {
			num_up++;
		} else {
			num_down++;
		}
	}
	if (num_up==0) {
		for(i=0; i<num_down-2; i++) {
			printf("great ");
		}
		if (num_down>1) {
			printf("grand ");
		}
		printf("parent\n");
		return;
	}
	if (num_down==0) {
		for(i=0; i<num_up-2; i++) {
			printf("great ");
		}
		if (num_up>1) {
			printf("grand ");
		}
		printf("child\n");
		return;
	}
	if (num_up==1 && num_down==1) {
		printf("sibling\n");
		return;
	}
	printf("%d cousin", MIN(num_up,num_down)-1);
	if (num_up!=num_down) {
		printf(" removed %d", ABS(num_up-num_down));
	}
	printf("\n");
}

int
main(void)
{
	int i;
	char str1[32], str2[32];

	for(i=0; i<300; i++) {
		people[i].name[0]=0;
		people[i].parent=-1;
		people[i].num_children=0;
		people[i].children=NULL;
	}
	while(1) {
		int all_done;
		int current=num_people;

		scanf("%s %s", str1, str2);
		if (!strcmp(str1,"no.child")) {
			break;
		}
		for(i=0; i<num_people; i++) {
			if (!strcmp(str1, people[i].name)) {
				current=i;
				break;
			}
		}
		if (current==num_people) {
			num_people++;
		}
		strcpy(people[current].name, str1);
		all_done=0;
		for(i=0; i<num_people; i++) {
			if (!strcmp(str2, people[i].name)) {
				int a = people[i].num_children;
				people[current].parent = i;
				people[i].children = realloc(people[i].children, (a+1)*sizeof(int));
				people[i].children[a] = current;
				people[i].num_children++;
				all_done=1;
				break;
			}
		}
		if (!all_done) {
			people[current].parent = num_people;
			strcpy(people[num_people].name, str2);
			people[num_people].num_children=1;
			people[num_people].children = malloc(sizeof(int));
			people[num_people].children[0] = current;
			num_people++;
		}
	}
	while(1) {
		if (scanf("%s %s", str1, str2)!=2) {
			break;
		}
		calc(str1, str2);
	}
	exit(0);
}