题解 | 家族树-牛客假日团队赛7D题

D-家族树_牛客假日团队赛7

https://ac.nowcoder.com/acm/contest/997/D

题目描述

Farmer John拥有一个传承数代的家族经营的农场，其中的奶牛的根源同样也可以在这个农场中追溯数代。通过检索古老的记录，Farmer John好奇于现在的这群奶牛互相之间是什么关系。请帮帮他！

输入描述:

输入的第一行包含N（1≤N≤100），之后是两头奶牛的名字。每头奶牛的名字都是由至多10个大写字母（A…Z）组成的字符串。Farmer John好奇于这行输入中这两头奶牛之间的关系。
接下来的N行，每行包含两头奶牛的名字X和Y，表示X是Y的母亲。

输出描述:

输出包含一行，表示输入第一行指定的两头奶牛之间的关系（简单起见，在下面的例子中，将这两头奶牛称为BESSIE和ELSIE）。下面是可能出现的不同种类的关系：如果BESSIE和ELSIE的母亲是同一头奶牛，输出“SIBLINGS”。BESSIE可能是ELSIE的直系后代，也就是说ELSIE是BESSIE的母亲（mother），外祖母（grand-mother），外曾外祖母（great-grand-mother），外曾外曾外祖母（great-great-grand-mother），等等。如果是这种情况，输出“ELSIE is the (relation) of BESSIE"，其中(relation)是适当的关系，比如“great-great-grand-mother”。如果ELSIE不是BESSIE的某个祖先或姐妹，但是是BESSIE的某个祖先的孩子，那么ELSIE就是BESSIE的姨母（aunt）。（译者注：英语原题在这里表述有误，供题人已作出声明。）如果ELSIE是BESSIE的外祖母的孩子，输出“ELSIE is the aunt of BESSIE”；如果ELSIE是BESSIE的外曾外祖母的孩子，输出“ELSIE is the great-aunt of BESSIE”；如果ELSIE是BESSIE的外曾外曾外祖母的孩子，输出“ELSIE is the great-great-aunt of BESSIE”；以此类推。如果BESSIE和ELSIE有任何其他的亲戚关系（也就是说，她们有共同的祖先），她们就是表姐妹，输出“COUSINS”。如果BESSIE和ELSIE既没有共同的祖先，其中任何一头也不是另一头的直系后代，输出“NOT RELATED”。

下图描述了上述关系，你只需考虑这些关系。观察到有一些像是“甥女（niece）”（姊妹的女儿）的关系是不必要的，这是由于如果BESSIE是ELSIE的甥女，那么ELSIE就是BESSIE的姨母。

示例1

输入

7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER

输出

BB is the great-aunt of AA

解答

我们用两个数组mother和daughter来记录每一对给出的关系(mother[i]是daughter[i]的母亲).
然后用比较暴力的方式找到a和b的最近的共同祖先(具体代码很容易懂)
用fara和farb分别记录他们和最近祖先的距离.
近的为前辈,远的为晚辈(输出是时候格式是前辈是晚辈的XXXX)
如果能找到,那么他们有关系
然后在按照fara和farb确定关系并且输出结果.

#include<bits/stdc++.h>

using namespace std;

string mother[150];
string daughter[150];
string a, b, amother ,bmother;

int n, fara, farb;
bool isR;

string getMother(string da){
    for(int i = 0; i < n; i++){
        if(daughter[i] == da){
            return mother[i];
        }
    }
    return "";
}

int main(){
    scanf("%d", &n);
    cin>>a>>b;
    for(int i = 0; i < n; ++i)  cin>>mother[i]>>daughter[i];
    amother = a;

    
    //这里是在找最近的共同祖先
    while(amother != ""){
        farb = 0;
        bmother = b;
        while(bmother != ""){
            if(bmother == amother){
                isR = 1;
                break;
            }
            bmother = getMother(bmother);
            farb++;
        }
        if(isR){
            break;
        }
        amother = getMother(amother);
        fara++;
    }
    //确定关系
    if(isR){
        if(fara > 1 && farb > 1){
            cout << "COUSINS" << endl;
        }else if(fara == 1 && farb == 1){
            cout << "SIBLINGS" << endl;
        }else{
            if(fara > farb){
                cout << b << " is the ";
                while(fara > 2){
                    cout << "great-";
                    fara--;
                }
                if(fara == 2 && farb == 0){
                    cout << "grand-mother of " << a << endl;
                }else if(fara == 2 && farb == 1){
                    cout << "aunt of " << a << endl;
                }else if(fara == 1){
                    cout << "mother of " << a << endl;
                }
            }else{
                cout << a << " is the ";
                while(farb > 2){
                    cout << "great-";
                    farb--;
                }
                if(farb == 2 && fara == 0){
                    cout << "grand-mother of " << b << endl;
                }else if(farb == 2 && fara == 1){
                    cout << "aunt of " << b << endl;
                }else if(farb == 1){
                    cout << "mother of " << b << endl;
                }
            }
        }
    }else{
        cout << "NOT RELATED" << endl;
    }

    return 0;
}

来源：o·Pav