题解 | 找出直系亲属

#include<iostream>
//由题目可以发现一个人一个父亲一个母亲，并不符合并查集合的用一个数组来存
//并且也要注意到如果用两个数组来存即两个并查集的话，在查找一个元素是否是另外一个元素的父母时非常的麻烦
//因为他的曾祖母可能是其父亲的母亲或者是其母亲的母亲存在交叉关系根本没法遍历
//但是如果能反过来存就能发现是能用一个数组表示的，即存每个结点的孩子
//所以本题的破题点就是用孩子数组来存
using namespace std;
const int N = 27;
int children[30];

void Union(int parent, int child) {
	children[parent] = child;
}

int find(int x, int y) {
	int res = 0;
	int tmp = x;
	//主要看一个是不是他的儿子,这里找到说明y是x的儿子
	while (children[tmp] != tmp) {
		if (tmp == y)return res;
		tmp = children[tmp];
		res++;
	}
	//万一y就是根节点的话要再判断一次
	if(tmp==y)return res;
	//这里res=0别忘了
	res = 0;
	tmp = y;
	//x是y的儿子
	while (children[tmp] != tmp) {
		if (tmp == x)return -res;
		tmp = children[tmp];
		res++;
	}
	if(tmp==x)return -res;
	return 0;
}

int main() {
	int n, m;
	while (cin >> n >> m) {
		//初始化并查集
		for (int i = 0; i <= 26; i++)children[i] = i;
		/*cin >> n >> m 会读取两个整数，并且会忽略掉输入后的换行符（\n）。但输入流中依然存在换行符。
这个换行符并没有被清空，接下来读取字符时（即 cin >> child >> father >> mother），cin 直接读取到了该换行符。*/
		while (n--) {
			getchar();
			char child, father, mother;
			cin >> child >> father >> mother;//读取字符串的时候就是这样
			if (father != '-')Union(father-'A', child-'A');
			if (mother != '-')Union(mother-'A', child-'A');
		}
		while (m--) {
			char x, y;
			cin >> x >> y;
			int res=find(x-'A', y-'A');
			if (res == 0)cout << '-' << endl;
			else if (res > 0) {
				if (res == 1)printf("parent\n");
				else if (res == 2)printf("grandparent\n");
				else if (res > 2) {
					while (res - 2 > 0) {
						printf("great-");
						res--;
					}
					printf("grandparent\n");
				}
			}
			else if (res < 0) {
				//这里的负号别漏了
				if (res == -1)printf("child\n");
				else if (res == -2)printf("grandchild\n");

				else if (res < -2) {
					while (res + 2 < 0) {
						printf("great-");
						res++;
					}
					printf("grandchild\n");
				}
			}
		}
	}

	return 0;
}