PTA 家谱处理

7-1 家谱处理 (24分)
人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例：

John
  Robert
    Frank
    Andrew
  Nancy
    David

家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他有两个子女Robert和Nancy，Robert有两个子女Frank和Andrew，Nancy只有一个子女David。

在实验中，研究人员还收集了家庭文件，并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例：

John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert

研究人员需要判断每个陈述语句是真还是假，请编写程序帮助研究人员判断。

输入格式:
输入首先给出2个正整数N（2≤N≤100）和M（≤100），其中N为家谱中名字的数量，M为家谱中陈述语句的数量，输入的每行不超过70个字符。

名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格，即他们是家谱中最早祖先（第一行给出的名字）的后代，且如果家谱中一个名字前缩进k个空格，则下一行中名字至多缩进k+2个空格。

在一个家谱中同样的名字不会出现两次，且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下，其中X和Y为家谱中的不同名字：

X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y

输出格式:
对于测试用例中的每句陈述语句，在一行中输出True，如果陈述为真，或False，如果陈述为假。

输入样例:

6 5
John
  Robert
    Frank
    Andrew
  Nancy
    David
Robert is a child of John
Robert is an ancestor of Andrew
Robert is a sibling of Nancy
Nancy is the parent of Frank
John is a descendant of Andrew

输出样例:

True
True
True
False
False

我的代码

#include<iostream>
using namespace std;
#include<string>
#include<time.h>
#include<vector>
struct Node
{
	string val;	
	vector<Node*> child;
	int level;
	Node* parent;
	Node() {};
	Node(string a,int l) :val(a), child(NULL),parent(NULL),level(l) {};
};
int space(string a) {
	int b = 0;
	for (int i = 0; a[i] == ' '; i++) {
		b++;
	}
	return b;
}
Node* BulidTree( int N) {	
	getchar();
	string up;
	getline(cin, up);
	Node* root = new Node(up,0),*p=root;
	//之前读取了一个根结点
	for(int i=0;i!=N-1;i++) {
		string a;
		getline(cin, a);	
		int gen = space(a);
		gen /= 2;		
		while (gen != p->level + 1) {
			p = p->parent;
		}
		Node* temp = new Node(a.substr(gen * 2, a.size()), gen);
		temp->parent = p;
		p->child.push_back(temp);		
		p = p->child[p->child.size()-1];
	}
	return root;
}
Node* find(Node* root,string name) {	
	if (root == NULL) return NULL;
	if (root->val == name)return root;
	Node* res=NULL;
	for (int i = 0; i != root->child.size(); i++) {
		Node* temp = find(root->child[i], name);
		if (temp != NULL) res = temp;
	}
	return res;
}
bool right(Node* tree,string name1,string realtionship, string name2) {		
	Node* p1 = find(tree, name1);
	Node* p2 = find(tree, name2);
	// 对于 sibling ,判断他们的parent是否相同
	if (realtionship.compare("sibling")==0) {
		if (p1 == tree || p2 == tree)
			return false;
		return  p1->parent->val.compare( p2->parent->val)==0;
	}
	// 对于 name1 是 name2 的parent, 判断name2的parent是否是name1
	if (realtionship == "parent") {
		if (p2 == tree) return false;
		return p2->parent->val == p1->val;
	}
	// 对于 name1 是 name2 的child, 判断name1的parent是否是 name2
	if (realtionship == "child") {
		if (p1 == tree)return false;
		return p1->parent->val == p2->val;
	}
	// 对于 name1 是 name2 的ancestor, 判断name2一路向上直到root是否有name1
	if (realtionship == "ancestor") {
		while (p2 != tree) {
			p2 = p2->parent;
			if (p2->val == name1)
				return true;
		}
		return false;
	}
	// 对于 name1 是 name2 的descendant, 判断name1沿路径向上一直到root是否有name2
	if (realtionship == "descendant") {		
		while (p1 != tree) {
			p1 = p1->parent;
			if (p1->val == name2)
				return true;
		}
		return false;
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	Node* tree = BulidTree(N);
	
	while (M--) {
		string name1, name2, realtionship,rubbish;		
		cin >> name1 >> rubbish >> rubbish>> realtionship >> rubbish >> name2;
		cout << (right(tree, name1, realtionship, name2) ? "True" : "False")<<endl;
	}

	///////////////////////////我的测试案例
	/*
	string ran[]{ "John","Robert","Frank","Andrew","Nancy","David" };
	string x[]{ "child","parent","sibling","descendant","ancestor" };
	int c = 100;
	srand((unsigned)time(NULL));
	while (c--) {
		
		string name1 = ran[rand() % 6];
		string name2 = ran[rand() % 6];
		string real = x[rand() % 5];
		if (name1 != name2) {
			cout << name1 << "  " << real << "  " << name2 << endl;
			cout << (right(tree, name1,real, name2) ? "True" : "False") << endl;
		}
	}
	*/
	///////////////////////////////////
	return 0;
}