题解 | #找出直系亲属#

在并查集的基础上进行多支路的修改

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

//本题父亲母亲都有，也没有说是独生子女，怎么说  强行递归？

//可以用一个visit数组来进行剪枝  每个人都是大写英文字母

const int MAXN = 30;

bool visit[MAXN]; 

class parent{
public:
	int mother;
	int father;
	parent():mother(-1),father(-1){}
	parent(int a, int b):mother(a),father(b){}
};

int Find(int x, vector<parent> &v, int target, int cengshu){//初步设计：没遇到就返回0，遇到了就返回寻找层数
	if(visit[x]){
		return 0;
	}else{
		visit[x] = true;
	}
	if(x == target){
		return cengshu;
	}
	if(v[x].mother == -1 && v[x].father == -1){
		return 0;
	}
	if(v[x].mother != -1){
		int direction1 = Find(v[x].mother, v, target, cengshu+1);
		if(direction1){//说明往母亲方向找到了 
			return direction1;
		}
	}
	if(v[x].father != -1){
		return Find(v[x].father, v, target, cengshu+1);//母亲那边没过的话，这边过了就是过了，没过就没过
	}
	return 0;
}

void Union(int x, int y, int z, vector<parent> &v){
	if(y != -1){
		v[x].mother = y;
	}
	if(z != -1){
		v[x].father = z;
	}
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(visit, false, sizeof(visit));
		vector<parent> v;
		for(int i=0; i<26; i++){
			v.push_back(parent());
		}
		string s;
		for(int i=0; i<n; i++){
			cin >> s;
			int y, z;
			if(s[1] != '-'){
				y = s[1]-'A';
			}else{
				y = -1;
			}
			if(s[2] != '-'){
				z = s[2]-'A';
			}else{
				z = -1;
			}
			Union(s[0]-'A', y, z, v);
		}
		for(int i=0; i<m; i++){//比如输入FA，是问F是A的谁 
			cin >> s;
			int find1 = Find(s[0]-'A', v, s[1]-'A', 0);
			memset(visit, false, sizeof(visit));
			if(find1){//从F往上找找到了A，说明F是A的后辈 
				while(find1 > 2){
					printf("great-");
					find1--;
				}
				if(find1 == 2){
					printf("grandchild\n");
				}else{
					printf("child\n");
				}
				continue;
			}
			int find2 = Find(s[1]-'A', v, s[0]-'A', 0);
			memset(visit, false, sizeof(visit));
			if(find2){//从A往上找找到了F，说明F是A的祖辈 
				while(find2 > 2){
					printf("great-");
					find2--;
				}
				if(find2 == 2){
					printf("grandparent\n");
				}else{
					printf("parent\n");
				}
				continue;
			}
			printf("-\n");
		}
	}
	return 0;
}