题解 | #找出直系亲属#

#include "bits/stdc++.h"

using namespace std;


class UnionSet{
public:
    int us[27];

    UnionSet() {
        memset(us,-1, sizeof(int)*27);
    }

    // 子女关系返回1，非直系返回-1,询问n1是n2的谁
    int find(char n1,char n2)
    {
        int node1=n1-'A';
        int node2=n2-'A';

        for (int i = node1,k=0; i>=0; i=us[i],k++) {
            if (i==node2)
            {
                return k;
            }
        }

        for (int i = node2,k=0; i>=0; ++k,i=us[i]) {
            if (i==node1)
                return -k;
        }

        return 0;
    }

    void setParent(string str)
    {
       int child=str[0]-'A';
       int parent1=(str[1]!='-' ? str[1]-'A' : -1);
       int parent2=(str[2]!='-' ? str[2]-'A' : -1);
        if (parent1!=-1)
            us[parent1]=child;
        if (parent2!=-1)
            us[parent2]=child;
    }
    string getRelationName(int n)
    {
        if (n==0)
        {
            return "-";
        }
        if (abs(n)==1)
        {
            return n==1 ? "parent":"child";
        }

        string ans= (n > 0 ? "grandparent" : "grandchild");

        while (abs(n)>2)
        {
            ans="great-"+ans;
            n>0 ? n-- : n++;
        }
        return ans;
    }

};
int main()
{
    int n,m;
    while (cin>>n>>m)
    {
        vector<string> input(n);
        UnionSet set;
        for (int i = 0; i < n; ++i) {
            cin>>input[i];
            set.setParent(input[i]);
        }

        vector<string> questions(m);
        for (int i = 0; i < m; ++i) {
            cin>>questions[i];

        }

        for (string question: questions) {
            cout<<set.getRelationName(set.find(question[0],question[1]))<<endl;
        }


    }


}