1504.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1504 on 2005-10-12 at 21:32:34 */ 
#include <cstdio>
#include <cstring>
#define  MAX  1024
#define  MAX_LEN  128

class BSTreeNode {
public:
	char name[MAX_LEN];
	int order;
	BSTreeNode *left;
	BSTreeNode *right;
	void init(char *s, int o) {
		left = NULL;
		right = NULL;
		order = o;
		strcpy(name, s);
	}
	int search(BSTreeNode *node) {
		BSTreeNode *p = this;
		int i;
        while(true) {
            i = strcmp(node->name, p->name);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    p->left = node;
                    return node->order;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    p->right = node;
                    return node->order;
                }
            } else {
				return p->order;
            }
        }
	}
};

class LinkedList {
public:
	int order;
	LinkedList *prev;
	int floor;
	void init(LinkedList *p, int o, int n) {
		prev = p;
		order = o;
		floor = n;
	}
	char* haveSameParent(LinkedList *x) {
		if(prev != x->prev) {
			return "False";
		} else {
			return "True";
		}
	}
	char* isAncestor(LinkedList *x) {
		LinkedList *y = x;
		if(floor >= x->floor) {
			return "False";
		} else {
			while(true) {
				y = y->prev;
				if(y->floor == floor) {
					if(y == this) {
						return "True";
					} else {
						return "False";
					}
				}
			}
		}
	}
	char* isParent(LinkedList *x) {
		if(this != x->prev) {
			return "False";
		} else {
			return "True";
		}
	}
};

int main()
{
	LinkedList family[MAX], *stack[MAX] = {NULL};
	BSTreeNode Node[MAX], *root, na, nb;
	char line[MAX_LEN], *p, nameA[MAX_LEN], nameB[MAX_LEN], r[MAX_LEN];
	int n, m, floor, floorP, len;
	int i, top, oa, ob;
	
	while(scanf("%d %d", &n, &m) == 2) {
		if(m == 0 && n == 0) {
			return 0;
		} else {
			top = 1;
			root = NULL;
			floor = -1;
			while(getchar() != '\n')
				;
			for(i = 0; i < n; i++) {
				gets(line);
				floorP = floor;
				for(floor = 0; floor < MAX_LEN; floor++) {
					if(line[floor] != ' ') {
						break;
					}
				}
				if(floor <= floorP) {
					top -= floorP - floor + 1;
				}
				stack[top++] = &family[i];
				p = line + floor;
				Node[i].init(p, i);
				if(root == NULL) {
					root = &Node[i];
				} else {
					root->search(&Node[i]);
				}
				family[i].init(stack[top-2], i, floor);
			}
			for(i = 0; i < m; i++) {
				scanf("%s %*s %*s %s %*s %s", nameA, r, nameB);
				len = strlen(nameB);
				nameB[len-1] = '\0';
				na.init(nameA, -1);
				nb.init(nameB, -1);
				oa = root->search(&na);
				ob = root->search(&nb);
				if(!strcmp(r, "child")) {
					printf("%s\n", family[ob].isParent(&family[oa]));
				} else if(!strcmp(r, "ancestor")) {
					printf("%s\n", family[oa].isAncestor(&family[ob]));
				} else if(!strcmp(r, "sibling")) {
					printf("%s\n", family[oa].haveSameParent(&family[ob]));
				} else if(!strcmp(r, "parent")) {
					printf("%s\n", family[oa].isParent(&family[ob]));
				} else {
					printf("%s\n", family[ob].isAncestor(&family[oa]));
				}
			}
			putchar('\n');
		}
	}
	
	return 0;
}