题解 | #找出直系亲属#

• 本题默认一个结点最多只有一个孩子
• 并查集：每个结点指向其孩子（不可压缩路径）

#include<iostream>
#include<string>
using namespace std;
const int maxn=27;
int son[maxn];

void Initial(){//初始化
    for(int i=0;i<maxn;i++){
        son[i]=i;
    }
    return ;
}

bool isson(int x,int y,string s){//y是否为x后代
    bool flag=false;
    int h=1;
    while(son[x]!=x){
        if(son[x]==y){
            flag=true;
            break;
        }
        h++;
        x=son[x];
    }
    if(flag==false)return false;
    else{
        if(h>=2)s="grand"+s;
        while(h>2){
            s="great-"+s;
            h--;
        }
        cout<<s<<endl;
    }
    return true;
}

 int main(){
     int  n,m;
     string s;
     
     while(scanf("%d %d",&n,&m)!=EOF){
         Initial();
         while(n--){
             cin>>s;
             if(s[1]!='-')son[s[1]-'A']=s[0]-'A';
             if(s[2]!='-')son[s[2]-'A']=s[0]-'A';
         }
         while(m--){
             cin>>s;
             int x=s[0]-'A';
             int y=s[1]-'A';
             if(!isson(x,y,"parent")&&!isson(y,x,"child")){
               printf("-\n");
             }
         }
     }
     return 0;
 }