题解 | #找出直系亲属#
找出直系亲属
https://www.nowcoder.com/practice/2c958d09d29f46798696f15ae7c9703b
//看很多大佬说这是模板题，一开始还真没想到，算是学习到了。刚开始想到两者想法，建树或当作图来做，
//但是都不太好写，最后还是看的讨论区才知道的做法。并且这个题目采用的并查集不能压缩路径，因为路径信息不能变
#include "stdio.h"
int Father[26];
int n,m;
void Init(){//初始化操作
for (int i = 0; i < 26; ++i) {
Father[i] = i;
}
}
int find(int x,int y,int &sum){//查找y
if(Father[x] != y && Father[x] != x){
++sum;
find(Father[x],y,sum);
} else if(Father[x] == y){
++sum;
} else if(Father[x] == x){
sum = 0;
}
return sum;
}
int main(){
while (scanf("%d%d\n",&n,&m) != EOF){
char p,l,r;
char temp1,temp2;
Init();
for (int i = 0; i < n; ++i) {
scanf("%c%c%c\n",&p,&l,&r);
if(l != '-' && r != '-'){
Father[l-'A'] = p - 'A';
Father[r-'A'] = p - 'A';
} else if(l != '-'){
Father[l-'A'] = p-'A';
} else if(r != '-'){
Father[r-'A'] = p-'A';
}
}
for (int i = 0; i < m; ++i) {
scanf("%c%c\n",&temp1,&temp2);
int q1 = temp1-'A',q2 = temp2-'A';
int sum = 0;//查找次数
sum = find(q1,q2,sum);
if(sum == 0){
sum = find(q2,q1,sum);
if(sum == 0){
printf("-\n");
continue;
}
else{
while (sum != 0){
if(sum == 1){
printf("child\n");
--sum;
} else if(sum == 2){
printf("grand");
--sum;
} else{
printf("great-");
--sum;
}
}
}
} else{
while (sum != 0){
if(sum == 1){
printf("parent\n");
--sum;
} else if(sum == 2){
printf("grand");
--sum;
} else{
printf("great-");
--sum;
}
}
}
}
}
}
Momenta公司福利 285人发布
