1386.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1386 on 2005-09-28 at 09:32:42 */ 
#include <cstdio>
#include <cstring>
#define  MAX  3005

class BSTreeNode {
public:
	char name[32];
	bool meet[MAX];
	bool knowAll;
	BSTreeNode *left;
	BSTreeNode *right;
	void init(char *s, int n) {
		strcpy(name, s);
		memset(meet, false, sizeof(meet));
		meet[n] = true;
		knowAll = false;
		left = NULL;
		right = NULL;
	}
	void add(BSTreeNode *node) {
		BSTreeNode *p = this;
		int result;
		while(true) {
			result = strcmp(p->name, node->name);
			if(result > 0) {
				if(p->left != NULL) {
					p = p->left;
				} else {
					p->left = node;
					break;
				}
			} else if(result < 0) {
				if(p->right != NULL) {
					p = p->right;
				} else {
					p->right = node;
					break;
				}
			}
		}
	}
	BSTreeNode* search(char *s) {
		BSTreeNode *p = this;
		int result;
		while(true) {
			result = strcmp(p->name, s);
			if(result == 0) {
				return p;
			} else if(result > 0) {
				if(p->left != NULL) {
					p = p->left;
				} else {
					return NULL;
				}
			} else {
				if(p->right != NULL) {
					p = p->right;
				} else {
					return NULL;
				}
			}
		}
	}
};

void change(BSTreeNode*, BSTreeNode*);
long N;

int main()
{
	long M, i;
	bool k;
	BSTreeNode *root, *Node[MAX], *meeti, *meetj;
	char name[32], per[32];
	
	for(i = 0; i < MAX; i++) {
		Node[i] = new BSTreeNode;
	}
	while(scanf("%ld %ld", &N, &M) == 2) {
		if(N == 0 && M == 0) {
			return 0;
		}
		root = NULL;
		for(i = 0; i < N; i++) {
			scanf("%s", name);
			Node[i]->init(name, i);
			if(root == NULL) {
				root = Node[i];
			} else {
				root->add(Node[i]);
			}
		}
		for(i = 0; i < M; i++) {
			scanf("%s %s", name, per);
			meeti = root->search(name);
			meetj = root->search(per);
			change(meeti, meetj);
		}
		k = true;
		for(i = 0; i < N; i++) {
			if(!(Node[i]->knowAll)) {
				k = false;
				break;
			}
		}
		if(k) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	
	return 0;
}

void change(BSTreeNode *a, BSTreeNode *b) 
{
	int i;
	bool temp, know = true;
	if(a->knowAll) {
		b->knowAll = true;
	} else if(b->knowAll) {
		a->knowAll = true;
	} else {
		for(i = 0; i < N; i++) {
			temp = a->meet[i] || b->meet[i];
			a->meet[i] = temp;
			b->meet[i] = temp;
			if(!temp) {
				know = false;
			}
		}
		a->knowAll = know;
		b->knowAll = know;
	}
}